重谈快速排序
——《数据结构与算法分析——C语言描述》
快速排序是最为常见的排序算法之一。谷歌、百度“快速排序”，会有很多快速排序的讲解和代码实现。但是这么多实现中，真正好的实现并不多见，快速排序思想很简单，但是实现起来有很多细节需要注意，稍不留意，就会出现错误或者效率降低。
快速排序有如下两个关键点：
1.枢纽元的选择
2.选定了枢纽元后，如何进行左右分割
这两点都会直接影响快速排序的效率，尤其是第二点，如果有些细节实现没有考虑清楚，会导致效率降低，甚至出现死循环。
选定了枢纽元后，进行左右分割有很多方法，只要最后分割的左右两部分元素满足小于或大于枢纽元即可。
常见的方法有挖坑填数法，具体实现网上有很多。但是大多数实现虽然完成了快速排序的功能，其运行效率并不是最好的，尤其是当待排序序列中的元素都是一样时，大多数的实现其时间复杂度退化为O(N*N)。而理想情况下，即便待排序序列中元素都一样时，快排的时间复杂度也应该为O(NlogN)。网上一些实现例子有：实现1、2、3、4。
对待排序序列进行分割思想很简单，实现起来有很多细节需要把握，稍不留意就会造成偏差，其原因在于我们选定枢纽元后，对待排序的分割操作是在原序列的上进行的，其空间复杂度为O(1)，这样会造成分割过程中一些细节的处理需要稍微谨慎。如果开辟一个临时的序列空间，用于暂存分割的序列，那么其空间复杂度为O(N)，时间复杂度没有提高，但是整个逻辑流程会变得很清晰，不会导致什么错误。
本文，我们是依照经典数据结构教材《数据结构与算法分析——C语言描述》中关于快速排序的讲解，对排序排序进行一实现。相关原理细节可以参阅本书。我们给出快速排序的实现，代码中添加一些快速排序的注释说明。
快速排序的最坏情况、最好情况、平均情况时间复杂度分析可以参照一些教材。我们这里重点在于算法的实现，不涉及数学方面的理论证明。
// 快速排序的实现 #include <iostream> using namespace std; // 交换函数 void swap(int& a, int& b) { int t = a; a = b; b = t; } // 该函数用于选择合适的枢纽元 // 具体做法是：选取三个元素，这三个元素为待排序序列中的第一个、最后一个、中间一个 // 去三个元素的中位数，作为快排的枢纽元 // 三个元素的选取也可以完全随机，但是没必要完全随机 // 该函数有两个功能：1.选择合适的枢纽元；2.将枢纽元交换到right-1位置 int Median3(int arr[], int left, int right) { // 取中间的坐标 int center = (left + right) / 2; // 对三个数进行排序 if (arr[left] > arr[center]) { swap(arr[left], arr[center]); } if (arr[left] > arr[right]) { swap(arr[left], arr[right]); } if (arr[center] > arr[right]) { swap(arr[center], arr[right]); } // 我们选arr[center]作为枢纽元 // arr[right]本身会大于等于枢纽元 // arr[left]本身会小于等于枢纽元 // 所以，我们不再将枢纽元置坐标置为right，而是置为right-1 // 在后续操作中，i的初始值设置为left+1，j的初始值设置为right-2 // 将枢纽元置于序列的后面，但不是最后一个——right，而是right-1 swap(arr[center], arr[right - 1]); // 返回枢纽元 return arr[right - 1]; } // 打印序列 void PrintArr(int arr[], int n) { for (int i = 0; i < n; ++i) { cout << arr[i] << ' '; } cout << endl; } // 插入排序 // 时间复杂度O(N*N) void InsertionSort(int arr[], int n) { if (n <= 1) { return; } for (int i = 1; i < n; ++i) { int tmp = arr[i]; int p = i - 1; while (p >= 0 && arr[p] > arr[p + 1]) { arr[p + 1] = arr[p]; --p; } arr[p + 1] = tmp; } } // 用于定义调用快速排序的最低元素个数：Cutoff+1 const int Cutoff = 3; // 快速排序实现 // 相关细节详见函数内注释说明 void QSort(int arr[], int left, int right) { int i = 0, j = 0; int pivot = 0; if (left + Cutoff <= right) // 如果元素个数大于等于Cutoff+1个，则调用快速排序 //if (left < right) // 如果没有插入排序的话 { pivot = Median3(arr, left, right); // Median3函数已经选择出枢纽元 // 并且将枢纽元交换到right-1的位置 i = left; // 注意这里还不是left+1，因为后面i的操作是++i j = right - 1; // 这里j还不是right-2，因为后面j的操作是--j for (;;) { while (arr[++i] < pivot); // 说明：++i操作，从left+1位置开始 // 如果i元素小于枢纽元，则i右移 // 不能使<=,因为如果真个序列的元素都是一个值，那么会造成时间复杂度为O(N*N) // <可以使时间复杂度为O(NlogN)，另一原因是++i // <导致=也会停止，进行交换 while (arr[--j] > pivot); // 参照++i // 不能使>=，因为同样会导致时间复杂度为O(N*N) if (i < j) { // 如果i和j没有交叉，此时，arr[i]大于等于pivot、arr[j]小于等于pivot // 交换两个数 // 如果arr[i]和arr[j]都等于pivot，也没关系，直接交换，因为上面是++i和--j swap(arr[i], arr[j]); } else { // 这里有可能是i=j // 如果出现i=j，说明arr[i]>=pivot,arr[j]<=pivot,又因为i=j，所以arr[i]=arr[j]，所以arr[i] = pivot // 如果i>j // 这里只能出现一种情况就是i=j+1 // 不管是i=j还是i>j，这一轮交换完毕 break; } } // for 循环结束之后进行交换 // 此时i指向的元素大于或等于枢纽元，j指向的元素小于或等于枢纽元 // 由于枢纽元此时在right-1位置，所以需要枢纽元和i元素交换 swap(arr[i], arr[right - 1]); // 完成一轮分割后，进行下一轮分割 // 分治递归 // 注意下一轮分割的左右部分都不包含上一轮的枢纽元，因为枢纽元是左右部分的中间元素，没必要包含 // 更为重要的是，如果包含了，有可能导致死循环，递归无法结束 // 此时枢纽元所在的位置为i QSort(arr, left, i - 1); QSort(arr, i + 1, right); } else // 调用插入排序 { InsertionSort(arr + left, right - left + 1); // 插入排序和快速排序的时间复杂度不同，各自有各自的特点和适用场合 } } // 对快速排序进行封装 void QuickSort(int arr[], int n) { QSort(arr, 0, n - 1); } int main() { int arr[] = {8, 1, 4, 9, 6, 3, 5, 2, 7, 0}; PrintArr(arr, sizeof (arr) / sizeof (*arr)); QuickSort(arr, sizeof (arr) / sizeof (*arr)); PrintArr(arr, sizeof (arr) / sizeof (*arr)); return 0; }
对于QSort中循环的实现：
i = left; // 注意这里还不是left+1，因为后面i的操作是++i j = right - 1; // 这里j还不是right-2，因为后面j的操作是--j for (;;) { while (arr[++i] < pivot); while (arr[--j] > pivot); if (i < j) { swap(arr[i], arr[j]); } else { break; } }
如果我们将其改为：
i = left + 1; // 一开始就将i置为left+1 j = right - 2; // 一开始就将j置为right-2 for (;;) { while (arr[i] < pivot) { ++i; } while (arr[j] > pivot) { --j; } if (i < j) { swap(arr[i], arr[j]); } else { break; } }
如果出现arr[i]=arr[j]=pivot情况，for循环将进入死循环，因为每次检查到arr[i]=pivot和arr[j]=pivot就会终止循环，并且i<j，相互交换，还都是pivot，无法终止。
一个改进的方法就是，我们在每次swap之后，修改i和j的值，对i自加，对j自减，这种操作是可行的，因为当前i和j元素交换，满足i元素小于等于pivot，j元素大于等于pivot。改进如下：
i = left + 1; // 一开始就将i置为left+1 j = right - 2; // 一开始就将j置为right-2 for (;;) { while (arr[i] < pivot) { ++i; } while (arr[j] > pivot) { --j; } if (i < j) { swap(arr[i], arr[j]); ++i; // 修改i --j; // 修改j } else { break; } }
完整的程序如下：
// 两个循环 #include <iostream> using namespace std; // 交换函数 void swap(int& a, int& b) { int t = a; a = b; b = t; } // 该函数用于选择合适的枢纽元 // 具体做法是：选取三个元素，这三个元素为待排序序列中的第一个、最后一个、中间一个 // 去三个元素的中位数，作为快排的枢纽元 // 三个元素的选取也可以完全随机，但是没必要完全随机 // 该函数有两个功能：1.选择合适的枢纽元；2.将枢纽元交换到right-1位置 int Median3(int arr[], int left, int right) { // 取中间的坐标 int center = (left + right) / 2; // 对三个数进行排序 if (arr[left] > arr[center]) { swap(arr[left], arr[center]); } if (arr[left] > arr[right]) { swap(arr[left], arr[right]); } if (arr[center] > arr[right]) { swap(arr[center], arr[right]); } // 我们选arr[center]作为枢纽元 // arr[right]本身会大于等于枢纽元 // arr[left]本身会小于等于枢纽元 // 所以，我们不再将枢纽元置坐标置为right，而是置为right-1 // 在后续操作中，i的初始值设置为left+1，j的初始值设置为right-2 // 将枢纽元置于序列的后面，但不是最后一个——right，而是right-1 swap(arr[center], arr[right - 1]); // 返回枢纽元 return arr[right - 1]; } // 打印序列 void PrintArr(int arr[], int n) { for (int i = 0; i < n; ++i) { cout << arr[i] << ' '; } cout << endl; } // 插入排序 // 时间复杂度O(N*N) void InsertionSort(int arr[], int n) { if (n <= 1) { return; } for (int i = 1; i < n; ++i) { int tmp = arr[i]; int p = i - 1; while (p >= 0 && arr[p] > arr[p + 1]) { arr[p + 1] = arr[p]; --p; } arr[p + 1] = tmp; } } // 用于定义调用快速排序的最低元素个数：Cutoff+1 const int Cutoff = 3; // 快速排序实现 // 相关细节详见函数内注释说明 void QSort(int arr[], int left, int right) { int i = 0, j = 0; int pivot = 0; if (left + Cutoff <= right) // 如果元素个数大于等于Cutoff+1个，则调用快速排序 //if (left < right) // 如果没有插入排序的话 { pivot = Median3(arr, left, right); // Median3函数已经选择出枢纽元 // 并且将枢纽元交换到right-1的位置 i = left; // 注意这里还不是left+1，因为后面i的操作是++i j = right - 1; // 这里j还不是right-2，因为后面j的操作是--j for (;;) { while (arr[++i] < pivot); // 说明：++i操作，从left+1位置开始 // 如果i元素小于枢纽元，则i右移 // 不能使<=,因为如果真个序列的元素都是一个值，那么会造成时间复杂度为O(N*N) // <可以使时间复杂度为O(NlogN)，另一原因是++i // <导致=也会停止，进行交换 while (arr[--j] > pivot); // 参照++i // 不能使>=，因为同样会导致时间复杂度为O(N*N) if (i < j) { // 如果i和j没有交叉，此时，arr[i]大于等于pivot、arr[j]小于等于pivot // 交换两个数 // 如果arr[i]和arr[j]都等于pivot，也没关系，直接交换，因为上面是++i和--j swap(arr[i], arr[j]); } else { // 这里有可能是i=j // 如果出现i=j，说明arr[i]>=pivot,arr[j]<=pivot,又因为i=j，所以arr[i]=arr[j]，所以arr[i] = pivot // 如果i>j // 这里只能出现一种情况就是i=j+1 // 不管是i=j还是i>j，这一轮交换完毕 break; } } // for 循环结束之后进行交换 // 此时i指向的元素大于或等于枢纽元，j指向的元素小于或等于枢纽元 // 由于枢纽元此时在right-1位置，所以需要枢纽元和i元素交换 swap(arr[i], arr[right - 1]); // 完成一轮分割后，进行下一轮分割 // 分治递归 // 注意下一轮分割的左右部分都不包含上一轮的枢纽元，因为枢纽元是左右部分的中间元素，没必要包含 // 更为重要的是，如果包含了，有可能导致死循环，递归无法结束 // 此时枢纽元所在的位置为i QSort(arr, left, i - 1); QSort(arr, i + 1, right); } else // 调用插入排序 { InsertionSort(arr + left, right - left + 1); // 插入排序和快速排序的时间复杂度不同，各自有各自的特点和适用场合 } } // 对快速排序进行封装 void QuickSort(int arr[], int n) { QSort(arr, 0, n - 1); } // 快速排序实现 // 相关细节详见函数内注释说明 void QSort2(int arr[], int left, int right) { int i = 0, j = 0; int pivot = 0; if (left + Cutoff <= right) { pivot = Median3(arr, left, right); i = left + 1; // 一开始就将i置为left+1 j = right - 2; // 一开始就将j置为right-2 for (;;) { while (arr[i] < pivot) { ++i; } while (arr[j] > pivot) { --j; } if (i < j) { swap(arr[i], arr[j]); ++i; // 修改i --j; // 修改j } else { break; } } swap(arr[i], arr[right - 1]); QSort(arr, left, i - 1); QSort(arr, i + 1, right); } else { InsertionSort(arr + left, right - left + 1); } } // 对QSort2封装 void QuickSort2(int arr[], int n) { QSort2(arr, 0, n - 1); } int main() { int arr[] = {8, 1, 4, 9, 6, 3, 5, 2, 7, 0}; PrintArr(arr, sizeof (arr) / sizeof (*arr)); QuickSort2(arr, sizeof (arr) / sizeof (*arr)); PrintArr(arr, sizeof (arr) / sizeof (*arr)); int arr2[] = {9, 9, 9, 9, 9, 9, 9, 9, 9, 9}; PrintArr(arr2, sizeof (arr2) / sizeof (*arr2)); QuickSort2(arr2, sizeof (arr2) / sizeof (*arr2)); PrintArr(arr2, sizeof (arr2) / sizeof (*arr2)); return 0; }
插入排序和快速排序
插入排序的时间复杂度是O(N*N)，快速排序平均的时间复杂度是O(NlogN)。但是并不是所有情况下快速排序都优于插入排序。当待排序元素个数较少时，更适宜用插入排序，比如程序中如果left+Cutoff>right时。
总结
以上是关于快速排序的相关内容。现在网上大多数快速排序的实现都并不是太好，存在或多或少的瑕疵，比如在分割过程中，如果当全部元素都是一样时，时间复杂度将为O(N*N)等。
快速排序的分割操作是在其自身位置进行的分割，容易导致分割过程中一些细节性问题。但是分割的思想很简单，目的是为了最大化的平分左右部分。