快速排序是不稳定的排序方法,平均时间复杂度为O(nlogn),空间复杂度为O(logn),最差时是有序或基本有序时,算法退化为冒泡排序,时间复杂度是O(n2)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | /* * 快速排序:选一个值pivokey(一般是第一个),小于pivokey放在左边,大于pivokey放在右边,分成两个序列,递归直到low >= high * 步骤: * 1,设定两个指针low,high。初值是0和数组长度-1,指定关键字pivokey * 2,从high所指的位置向前找,找到一个比pivokey小的,和关键字交换值(arr[low] = arr[high]) * 3,从low所指的位置向后找,找到一个比pivokey大的,和关键字交换值 * 4,直到low>=high,把关键字赋值arr[low]=pivokey * 5,递归分出的两个序列[lowStart,low-1] [low+1,highEnd] * */ int[] quickSort(int[] arr, int low, int high) { //为后面的递归使用 int lowStart = low; int highEnd = high; if (low < high) { int pivokey = arr[low]; while (low < high) { //如果都是大于pivokey,high指针往前移 while (low < high && arr[high] > pivokey) { high--; } //这里low++是先把arr[low]赋值为arr[high],再low+=1,因为这个值是比pivokey小的,下一次不用比较了 if (low < high) arr[low++] = arr[high]; //如果都是小于pivokey,low指针往后移 while (low < high && arr[low] < pivokey) { low++; } //这里的high--和上面同理 if (low < high) arr[high--] = arr[low]; } arr[low] = pivokey; quickSort(arr, lowStart, low - 1); quickSort(arr, low + 1, highEnd); } return arr; } |
7条评论
感谢楼主分享的好文章!!!
说的很详细,谢谢分享!
和c++的算法差不多!!
恩,都一样。。
忙的人才充实啊,.太闲了就无聊了……
存在bug,若待排序数组为“4,3,2,1”,则会抛错误滴。
挺不错的!