对于包含n个数的输入数组来说快速排序是一种最坏情况时间复杂度为Θ(n^2) 的排序算法。虽然最坏情况时间复杂度很差但是快速排序通常是实际排序应用中最好的选择因为它的平均性能非常好另外它还能够进行原址排序甚至在虚存环境中也能很好的工作。快速排序的描述快速排序使用了分治递归的思想过程较为抽象下面是对一个典型的子数组A[p..r]进行快速排序的过程从A[p..r]选出一个任意的值A[q],使得A[p..r]划分为两个可能有一个为空子数组A[p...q-1]和A[q1..r]使得A[p...q-1]中的所有元素都小于或等于A[q]并且A[q1..r]中的所有元素都大于或等于A[q]。其中如何选择A[q]也是一个重要的过程。然后再重新递归调用子数组A[p...q-1]、A[q1..r]重复上面的过程直到子数组不能再划分时原数组排序完毕下面使用伪代码描述一下整个过程快速排序的关键部分是找到A[q]并划分两边的子数组partition(A,p,r) xA[r] //我们可以默认选择最后一个元素为A[q]当然选其他的也可以 ip-1 for j p to r-1 if(A[j]x ii1 exchange A[i] with A[j] exchange A[i1] with A[r] return i1这部分程序是用于划分A[q] 两边的值使A[p...q-1]中的所有元素都小于或等于A[q]并且A[q1..r]中的所有元素都大于或等于A[q]并返回下标q。下面我们用图展示一下整个过程上图显示了划分子程序如何在一个包含8个元素的数组上进行操作的过程。程序开始总是先以数组的最后一个元素作为主元并围绕主元来划分两边的子数组。在划分好两个子数组后我们需要递归调用子数组再次进行划分直到子数组不再能划分整个数组就排好序了。我们可以先用伪代码描述一下这个过程quicksort(A,p,r) if q r qpartition(A,p,r) quicksort(A,p,q-1) quicksort(A,q1,r)至此快速排序描述完毕快速排序的性能快速排序的运行时间依赖于划分是否平衡而平衡与否又依赖于用于划分的元素。如果划分是平衡的那么快速排序的性能就接近Θ(nlgn),如果划分不平衡那么快速排序的性能就接近Θ(n^2)。当划分产生的俩个子数组包含一个n-1的数组和0个元素的数组时快速排序划分不平衡。当每一次递归调用划分子程序都产生这种情况时快速排序的性能达到最差。但是划分过程中有时是平衡的有时是不平衡的。只要不是全部的递归调用都产生不平衡的子数组那么快速排序的性能还是能保持在Θ(nlgn)。但是如果划分过程不平衡的次数越多那么他的时间复杂度Θ(nlgn)的常数项就会越大。最后贴上测试的代码#include iostream using namespace std; int partition(int arr[], int p, int r) { int mark arr[r]; //分界线 int k p; for (int i p; i r; i) { if (arr[i] mark) { int temp arr[k]; arr[k] arr[i]; arr[i] temp; k; } } int temp arr[k]; arr[k] arr[r]; arr[r] temp; return k; } void quickSort(int arr[], int p, int r) { if (p r) { int qpartition(arr, p, r); //以arr[r]为划分分为小于和大于 quickSort(arr, p, q - 1); quickSort(arr, q 1, r); } } int main() { int arr[8] { 2 ,8 ,7 ,1 ,3 ,5, 6 ,4 }; quickSort(arr, 0, 7); for (int i 0; i 10; i) { cout arr[i] endl; } return 0; }