快速排序算法

算法思想

快速排序（quicksort）是在实践中最快的已知排序算法，快速排序算法是一种分治的递归算法，对数组S进行快速排序的步骤：

（1）如果S中的元素个数是0或者1，则返回；

（2）取S中任一元素v，称之为枢纽元（pivot）；

（3）将S - { v }分成一个不相交的集合，S1 = { x属于S - { v } | x <= v }，S2 ={ x属于S - { v } | x >= v }；

（4）quicksort( S1 )，v，quicksort( S2 )。

简单的说：在数组中选择一个枢纽元，然后将数组划分成两部分，左边的部分元素全部小于等于枢纽元，右边的部分全部大于等于枢纽元，在左右两边递归的进行这种分割。在快速排序中如何选择枢纽元是一个重要的决策，理想的情况是分割出来的两个集合大致相等，约等于原集合的一半。

算法过程

首先给出算法导论中的快排算法：

quicksort(A,p,r)
 if p < r
   then q = PARTITION(A,p,r)
        quicksort(A,p,q - 1)
        quicksort(A,q + 1,r)

其中A是待排序数组，p和r分别是本次处理的左边界和右边界。算法的重点是PARTITION(A,p,r)，它将A分割成S1和S2，返回的q是枢纽元保存的位置。算法导论中给出的PARTITION(A,p,r)是单边移动的，也就是说每次只从左边移动分割数组。

PARTITION(A,p,r)
 x = A[r]
 i = p -  1
 for j = p to  r -1
   if A[j] <= x
      then i = i + 1;
           exchange A[i] <--> A[j]
exchange A[i + 1] <--> A[r]
return i + 1

上面的算法中，总是选择最右边元素作为枢纽元，j从左边界开始遍历数组，A[j]小于等于枢纽元，就将A[j]与A[i + 1]交换，因为A[i + 1]大于枢纽元或者就是当前调整的元素（A[j]）。i的下一个元素是大于枢纽元或者是A[j]。下面以序列：2 8 7 1 3 5 6 4为例，演示上述过程：

最右边的元素4被选为枢纽元，i初始为p -1，i的下一个元素大于枢纽元或者是正在处理的元素，图中j的位置表示下一趟要处理的元素。红色矩形里的元素表示已经分割过的小于枢纽元的元素。

描述一下图中的过程：初始时i = -1，j = 0

（1）第一次，2 < 4，将i加1，交换A[i] <--> A[j]，其实就是2和它自己交换；++j

（2）第二次，8 > 4，i不变，++j

（3）第三次，7 > 4，i不变，++j

（4）第四次，1 < 5，++i，A[i] <--> A[j]，也就是1和8交换；++j

（5）第五次，3 < 4，++i，A[i] <--> A[j]，也就是3和7交换；++j

（6）第六次，5 > 4，i不变，++j

（7）第七次，6 > 4，i不变，++j

一次分割完成，A[i]是最后一个小于枢纽元的元素，A[i + 1]则大于枢纽元，所以将A[i + 1]与A[r]交换，就将数组A分割成三部分：S1，枢纽元，S2，可以看到，枢纽元已经在正确的位置上了。代码实现如下，这个代码将PARITION合并到了quicksort里了：

void quicksort(int* a,int p,int r) {
    //如果是0或者1个元素，就返回
    if(p >= r)
        return ;
    int i = p - 1;
    int j;
    int pivot = a[r];
    //<=i指向的是小于pivot的元素
    for(j = p; j < r; j++) {
        if(a[j] <= pivot) {
            ++i;
            swap(&a[i],&a[j]);
        }
    }
    //没有必要使用q，是为了跟上述的算法一致，q保存的是枢纽元
    int q = i + 1;
    swap(&a[q],&a[right]);
    //递归调用
    quicksort(a,p,q - 1);
    quicksort(a,q + 1,r);
}

选取枢纽元

快速排序算法的性能依赖于枢纽元的选取，我们希望每次分割都能得到两个大小相等的集合，可是如果枢纽元选取不当的话，最坏的情形是S1和S2中有一个为空，那么快速排序的时间花费是O(n^2)。选取第一个元素或者最后一个元素绝对是愚蠢的，如果序列是预排序的，那么最坏的情况就会发生；选取前两个互异关键字中较大者作为枢纽元，和只选取第一个作为枢纽元具有同样的害处。一种安全的策略是随机选择枢纽元，但这并不是非常好的做法。

枢纽元最好是选择数组的中值，但是这很困难，这样的中值可以通过随机选取三个元素，并用它们的中值作为枢纽元，由此得到三数中值分割法。

三数中值分割法

随机选择三个数并没有太大的帮助性，一般的做法是选择左端、右端和中心点三个数的中值作为枢纽元，显然三数中值分割法可以消除预排序输入的最坏情形。前面讲的分割过程是单边的，下面将一个双边分割的过程，双边分割的过程如下：

（1）将枢纽元与最后一个元素交换，这样枢纽元就能离开待分割的数据段；

（2）i从第一个元素开始，j从倒数第二个元素开始，因为最后一个元素师枢纽元。

（3）当i在j的左边时，i右移，移过那些小元素，一旦i碰到一个大元素立即停止；j左移，移过那些大元素，一旦j碰到一个小元素立即停止；

（4）此时i指向一个大元素，j指向一个小元素；如果i在j的左边，交换两个元素，效果相当于将一个大元素移到右边，同时将一个小元素移到左边。

还是需要具体的过程来演示，使用序列：2 8 7 1 6 3 9 5 4，使用三数中值策略选择枢纽元6，将6与最后一个元素交换，得到如下序列及i，j的初始位置

i2 8 7 1 4 3 9 j5 | 6

第一次：i右移，直到遇到元素大于枢纽元，j左移，直到遇到元素小于枢纽元 2 i8 7 1 4 3 9 j5 | 6

交换i和j指向的元素，第一次交换后得到的序列（和上一行公用i和j）： 2 i5 7 1 4 3 9 j8 | 6

第二次：i右移，j左移：2 5 i7 1 4 j3 9 8 | 6

交换i和j指向的元素， 2 5 i3 1 4 j7 9 8 | 6

第三次：i右移，j左移：2 5 31 j4 i79 8 | 6

可以看到i和j已经交错了，分割结束。可以看出，<i位置上都是小于枢纽元的元素，i位置是第一个大于枢纽元的元素，所以将i与右端枢纽元交换，一次分割完成

2 5 31 469 8 7

等于枢纽元的处理

前面考虑的所有元素跟枢纽元都是互异的，那么如果i、j遇到等于枢纽元的元素应该怎么办？有一点是确定的，i和j应该做相同的动作，否则分割将偏向一方。考虑一种极端的情况：所有元素都相等。

如果i和j都停止，那么i和j将进行很多次的交换，虽然这没有意义，但是i和j将在中间交错，其效果是划分了两个相等的子数组，运行时间是O(N logN);

如果i和j都不停止，那么i将移动到倒数第二个位置，交换后，枢纽元就在倒数第二个位置上，这样划分了两个极不平衡的子数组。运行时间是O(N^2);

所以，我们发现进行不必要的交换得到两个均衡的子数组要比蛮干冒险得到两个不均衡的数组要好，因此，如果i和j遇到等于枢纽元的元素，那么就让它们都停止。

选取中值

选取三个数的中值，比较容易的做法是对三个数进行排序，这样A[mid]自然就是想要的枢纽元。同时，这样做还有一个好处，左端的元素和右端的元素都已经处在了正确的位置上。然后交换A[mid]和A[right - 1]，这样使得枢纽元离开待分割序列。分割时，i从left + 1开始，j从right - 2开始。

int median3(int A[],int left,int right) {
    int mid = (left + right) / 2;
    if(A[left] > A[mid])
        swap(&A[left],&A[mid]);
    if(A[left] > A[right])
        swap(&A[left],&A[right]);
    if(A[mid] > A[right])
        swap(&A[mid],&A[right]);
    //枢纽元和A[right - 1]交换
    swap(&A[mid],&A[right - 1]);
    return A[right - 1];
}

void quicksort(int *A,int left,int right) {
    if(left >= right)
        return ;

    int pivot = Median3(A,left,right);
    //如果小于等于三个元素的话，选中值时已经排序完成
    if((right - left) < 3)
        return;

    int i = left;
    int j = right-1;

    for(;;) {
        while(A[++i] < pivot);
        while(A[--j] > pivot);
        if(j < j) 
            swap(&A[i],&A[j]);
        else
            break;

    }
    swap(&A[i],&A[right - 1]);
    quicksort(p,left,i - 1);
    quicksort(p,i + 1,right);
}

由于A[left] <= pivot，所以j如果移动到了left就会停止，同样，i如果移动到了right - 1(枢纽元的位置)也会停止，防止了越界的产生。有一点需要注意的是，对于小数组（N<=20），快速排序不如插入排序好。快速排序是递归的，递归到最后几层的时候，基本上都是小数组。因此，一种好的策略是，当N=10时，不再采用快速排序，而使用插入排序。

时间复杂度分析

快速排序是递归的，每次将数组分成一个长度为i的子数组和长度为N-i-1的子数组，所以快速排序的时间等于两个递调用的时间加上线性分割的时间：

T(N) = T(i) + T(N - i -1) + cN

最坏情形分析

最快的情形就是每次分割，其中一个子数组为空，另一个为N-1，此时

T(N) = T(N - 1) + cN (1)

T(N - 1) = T(N -2) + c(N - 1)

T(N - 2) = T(N - 3) + c(N - 2)

......

T(2) = T(1) + c(2)

将上面式子相加得到：T(N) + T(N - 1) + T(N - 2) + ... + T(2) = T(N - 1) + T(N - 2) + ... + T(1) + c((N - 1) + (N -2) +... + 3 + 2)

T(N) = T(1) + c（2 + 3 +．．．+ N -1） = O( N^2)

最好情形分析

最好的情形就是每次分割成两个大小相等的子数组，约等于N/2

T(N) = 2T(N / 2) + cN (*)

等式两边同时除以N，得到：

T(N) / N = T(N / 2) / (N / 2) + c (**)

重复上面的步骤：

T(N / 2) / (N / 2) = T(N / 4) / (N / 4) + c (***)

T(N / 4) / (N / 4 ） =T(N / 8) / (N / 8) + c (****)

.....

T(2) / 2 = T(1) / 1 + c

将上述所有式子相加：

T(N) / N +T(N / 2) / (N / 2) +T(N / 4) / (N / 4)...+ T(2) / 2 =T(N / 2) / (N / 2) +T(N / 4) / (N / 4) + ... T(1) + clogN(递归logN次，所以上面有logN个式子)

将相同的项消去，得到：T(N) / N = T(1) + clogN

T(N) = cNlogN + N = O(NlogN)

平均情形分析

假设每次分割总产生9:1的分割，虽然这看上去很不均衡，其分割如下图所示

只有一点需要说明，那就是每次层最多需要cn时间，所以平均数回见复杂度是：O(NlogN)。

转载请注明出处：喻红叶《快速排序算法》