前言

快速排序的平均情况下是O(nlogn)，但是一般都比其他运行时间为O(nlogn)的算法都要快，因为它隐藏的常数因子比较小，但是在最坏情况之下，快速排序的运行时间是O(n²)。

快速排序过程

快速排序采用的思想是分治思想，就像合并排序算法的思想一样，合并排序算法是从数组的中间开始分治，直到分为N个分组，最后分别合并N个分组的解。如下图，有原始数组A = {1, 3, 4, 5, 7, 2, 6, 8, 0}

快速排序是找出一个元素（理论上可以随便找一个）作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值都不小于基准值，如此作为基准的元素调整到排序后的正确位置。递归快速排序，将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正确位置，排序完成。所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。

基准

基准的挑选会影响到算法的性能，一般情况将序列的第一个元素作为基准。

分区算法

设两个指针left和right，一个从左往右扫描，一个从右往左扫描；对于左指针，如果左指针所指的元素的值小于或者等于基准值，那么指针往右移一位，如果大于基准值，则和基准值交换；同理，对于右指针，如果右指针所指的元素的值大于或者等于基准值，那么指针往左移一位，如果小于基准值，则和基准值交换。代码如下：

view plaincopy to clipboardprint?
    
int Partition(int A[], int p, int r)  
    
{  
    
    int privot = A[p];  //基准   
    
    // 设两个指针   
    
    int left = p;   //从左往右扫描   
    
    int right = r;  //从右往左扫描   
    
      
    
    while (right > left)  
    
    {  
    
        while (right > left && A[right] >= privot)    
    
        {  
    
            right--;  
    
        }  
    
  
    
        A[left] = A[right];  
    
  
    
        while (right > left && A[left] <= privot)  
    
        {  
    
            left++;  
    
        }  
    
  
    
        A[right] = A[left];  
    
    }  
    
  
    
    A[left] = privot;  
    
    return left;  
    
}  
    
  
    
void QuickSort(int A[], int p, int r)  
    
{  
    
    int pivot;  
    
  
    
    if (r > p)  
    
    {  
    
        pivot = Partition(A, p, r);  
    
        QuickSort(A, p, pivot-1);  
    
        QuickSort(A, pivot+1, r);  
    
    }  
    
}  
int Partition(int A[], int p, int r){int privot = A[p];  //基准// 设两个指针int left = p;   //从左往右扫描int right = r;  //从右往左扫描while (right > left){while (right > left && A[right] >= privot){right--;}A[left] = A[right];while (right > left && A[left] <= privot){left++;}A[right] = A[left];}A[left] = privot;return left;}void QuickSort(int A[], int p, int r){int pivot;if (r > p){pivot = Partition(A, p, r);QuickSort(A, p, pivot-1);QuickSort(A, pivot+1, r);}}

性能分析

最好情况

每次基准的最终位置都是在数组中间位置，从而使规模为N的问题分为2个规模为N/2的问题，即T(n) = 2T(n/2) + Θ(n)，用递归树分析或者主定理得到时间T(n) = O(nlogn)。

最坏情况

每次基准的最终位置都是第一个位置，从而规模为N的问题分为一个规模为N-1的问题，即T(n) = T(n-1) + Θ(n),用递归树分析可得运行时间T(n) = O(n²)。

平均情况

假设规模为N的问题分为一个规模为9/10N的问题和规模为1/10N的问题，即T(n) = T(9n/10) + T(n/10) + Θ(n),用递归树分析可得T(n) = O(nlogn)，而且比分区9:1要更平均（也就是情况更好）的概率为80%，所以在绝大部分情况下快速排序算法的运行时间为O(nlogn)。