首页 > 代码库 > 快速排序
快速排序
快速排序是递归的思路谈起来是很简单的：
（1）当待排元素S个数为1的时候，什么也不做。
（2）在待排元素S中取一个元素作为枢纽pivot。
（3）将待排元素分成三份：小于pivot的元素S1、pivot它自己、大于pivot的元素S2。
（4）对小于pivot的元素S1进行快速排序，对大于pivot的元素S2进行快速排序。
但是，具体实现这个思路的时候，是比较复杂的。
对于（2），我们取枢纽元的时候，决定了S1和S2的个数。我们希望S1和S2各占S的一半左右，如此的话，元素可以被细分logN次，每次两份，就是2*logN，对每一份的比较是线性的，为N，快速排序的时间复杂度为O(NlogN)。
但是如果每次S1和S2极度不平衡，例如S2大大超过S1，考虑最坏的情况，S1每次0个，其余都在S2中，则元素要被分N-1次，每次的比较也是线性的，为N，则快速排序的时间复杂度为O(N^2)。
所以枢纽的选择很重要，最糟糕的选法是把第一个元素当成枢纽，在待排元素基本有序的情况下，快速排序的时间复杂度是二次的。最安全的选法是随机选择元素当枢纽。另外有一种流行的并且安全的方法是Median-of-Three Partitioning，其实就是选择第一个，中间一个和最后一个元素，然后把这三个位置根据大小进行排序，并把最小值放在最左边，最大值放在最右边，中间的值放在中间，作为枢纽。之后，我们把枢纽与当前待排序集合的倒数第二个位置（或者最后）交换，那么枢纽右边的值自然是大于枢纽的，不用考虑。方便我们将来的分割。
对于（3），当我们分割元素的时候，要考虑当元素等于枢纽的值的情况。考虑当待排数组的元素的值完全相同，如果我们将枢纽视单独视为划分到S1或S2，那么同样会造成O(N^2)的时间复杂度。所以我们在分割的时候，i和j遇到等于枢纽的情况也要停下。
另外，当我们使用Median-of-THree分割法的时候，遇到少于三个元素的，我们将它丢到插入排序去处理。如此避免我们在快排的实现中考虑额外的特殊情况。这个做法依据这样一个工程实践：
对于很小的数组（N<=20），快速排序不如插入排序好。对于小的数组，我们不递归使用快速排序，而以插入排序这样对小数组有序的排序算法来取代。使用这种策略，针对自始至终使用快速排序的情况，可以节省大约15%的运行时间。
实现的代码如下：
1 #include <cstdio> 2 #include <cstdlib> 3 4 #define MINLENGTH 3 5 6 typedef int Item; 7 // inlineʹSwapÄÚÁªÕ¹¿ª¡£Ìá¸ß³ÌÐòЧÂÊ¡£ 8 void inline 9 Swap(Item* a, Item* b)10 {11 *a ^= *b;12 *b ^= *a;13 *a ^= *b;14 } 15 // ÔÚarrÖÐÈ¡×óÖÐÓÒÈý¸öλÖ㬱Ƚϡ£pivotÈ¡ÖмäÖµ£¬½«pivot·ÅÔÚright-1µÄλÖÃÉÏ¡£16 // leftµÄλÖÃСÓÚpivot£¬rightµÄλÖôóÓÚpivot¡£ 17 Item18 Median3(Item arr[], int left, int right)19 {20 int center = (left + right) / 2;21 22 if (arr[left] > arr[center]) {23 Swap(&arr[left], &arr[center]);24 }25 if (arr[left] > arr[right]) {26 Swap(&arr[left], &arr[right]);27 }28 if (arr[center] > arr[right]) {29 Swap(&arr[center], &arr[right]);30 }31 32 Swap(&arr[center], &arr[right-1]);33 return arr[right-1];34 }35 36 void37 InsertSort(int arr[], int len)38 {39 for (int i = 1; i < len; i++) {40 int tmp = arr[i];41 int j;42 for (j = i; j >= 1 && arr[j-1] > tmp; j--) {43 arr[j] = arr[j-1];44 }45 arr[j] = tmp;46 }47 }48 // ÕâÀïÑ¡ÓÃi£¬jÓöµ½µÈÓÚpivotµÄÇé¿öÏÂÍ£Ö¹£¨ÒòΪÈç¹û²»Í£Ö¹£¬ÄÇ»á´ïµ½O(N^2)¡££©49 // ÁíÍ⣬³ÌÐò¿¼ÂÇ´ýÅÅÊý×Ö²»ÉÙÓÚ3¸öµÄÇé¿ö¡£ÉÙÓÚ3¸öµÄ»°£¬ÐèÒª¿¼ÂǶîÍâµÄÌØÊâÇé¿ö¡£ 50 void 51 QSort(Item arr[], int left, int right) 52 {53 if (right - left >= MINLENGTH) {54 int pivot = Median3(arr, left, right);55 int i = left;56 int j = right - 1;57 for ( ; ; ) {58 while (arr[++i] < pivot) {}59 while (arr[--j] > pivot) {}60 if (i < j) {61 Swap(&arr[i], &arr[j]);62 } else {63 break;64 }65 }66 Swap(&arr[i], &arr[right-1]); // ½«pivot·ÅÔÚiµÄλÖÃÉÏ¡£ 67 QSort(arr, left, i - 1);68 QSort(arr, i + 1, right);69 } 70 else {71 InsertSort(arr + left, right - left + 1);72 }73 }74 75 void76 QuickSort(Item arr[], int len)77 {78 QSort(arr, 0, len-1);79 }80 81 int 82 main(int argc, char** argv)83 {84 Item arr[6] = {17, 11, 2, 23, 5, 7};85 86 QuickSort(arr, 6);87 88 for (int i = 0; i < 6; i++) {89 printf("%d\t", arr[i]);90 }91 printf("\n");92 93 system("pause");94 95 return 0;96 }
快速排序