7.3.2 快速排序

快速排序是对冒泡排序的改进。其基本思想是基于分治法：在待排序L[1...n]中任取一个元素privot作为基准，通过一趟排序将待排序表划分为独立的两部分L[1...k-1]和L[k+1...n],使得L[1...k-1]中所有元素小于privot，L[k+1...n]中所有元素大于或等于privot，则privot最终放在了其最终位置L(k)上，这个过程称作一趟快速排序。而后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素为空为止，即所有元素放在了其最终位置上。

注意：在快速排序算法中，并不产生有序子序列，但每趟排序后将一个元素（基准元素）放到其最终的位置上。

首先假设划分算法已知，记为Partition()，返回的是上述中的K，注意到L(k)已经在最终的位置，所以可以先对表进行划分，而对两个表调用同样的排序操作。因此可以递归地调用快速排序算法进行排序，具体的程序结构如下：

void QuickSort(ElemType A[],int low ,int high){
    if(low<high){
        int pivotpos=Partition(A,low,high);//划分
        QuickSort(A,low,pivotpos-1);//依次对两个子表进行递归排序
        QuickSort(A,pivotpos-1,high);//依次对两个子表进行递归排序
    }
}
从上面的代码也不难看出快速排序算法的关键在于划分操作，同时快速排序算法的性能也主要取决于划分操作的好坏。
严版的划分方式：假设每次总是以当前表中第一个元素作为枢轴值（基准）对表进行划分，则必须将表中比枢轴值大的元素向右移动，比枢轴值小的元素向左移动，使得一趟partition()操作之后，表中的元素被枢轴一分为二。

int Partition(ElemType A[],int low,int high){
    ElemType pivot=A[low];
    while(low<high){
        while(low<high&&A[high]>=pivot)
            high--;
        A[low]=A[high];//从high向Low 查找小于枢轴的元素，将比枢轴值小的元素移动到左端,如果不存在，则A[low]=A[low]即无操作
        while(low<high&&A[low]<=pivot)
            low++;
        A[high]=A[low];//从low向high查找大于枢轴的元素，将比枢轴值大的元素移动到右端，如果不存在,则A[high]=A[high]即无操作
    }
    A[low]=pivot;//枢轴元素存放在最终位置
    return low;
}

对算法的最好理解就是手动地模拟一遍算法。

Partition(A,0,5) 第一次外层while循环 low=0 high=5 pivot=3

0<5&&7>=3 即 low<high&&A[high]>=3

high=5,4,3,2 从后往前查找小于等于3的元素，找到high=2 A[2]=2

A[0]=A[2]=2;   

0<2&&3<=3 即 low<high&&A[low]<=3

low=0,1 从前往后查找大于3的元素，找到low=1 A[1]=8

A[2]=A[1]=8;   

第二次外层while循环 1<2 即low<high

1<2&&A[high]>=3

high=2,1 从后往前 查找小于等于3的元素，没有找到 high=1

A[1]=A[1]=8 

1<1&&A[1]<=3 即low<high&&A[1]<=3 条件不成立 循环结束 A[1]=pivot=3

通过一趟排序，将待排序表划分为独立的两个部分

2

空间效率：由于快速排序是递归的，需要借助一个递归工作栈来保存每一层递归调用的必要信息，其容量应与递归调用的最大深度一致。

最好情况下为log2(n+1)；

最坏情况下，因为要进行n-1次递归调用，所以栈的深度为O(n);

平均情况下，栈的深度为O(log2 N).

因而空间复杂度在最坏情况下为O（n），平均情况下为O(log2 N)

时间效率：

快速排序的运行时间与划分是否对称有关，而后者又与具体使用的划分算法有关。快速排序的最坏情况发生在两个区域分别n-1个元素和0个元素时，这种最大程序的不对称性若发生在每一层递归上，即对应于初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度o(n^2)。

有很多方法可以提高算法的效率。一种方法是当递归过程中划分得到的子序列规模较小时，不要再继续递归调用快速排序，可以直接采用插入排序算法进行后续的排序工作。另一种方法就是尽量选取一个可以将数据中分的枢轴元素。如从序列的头尾以及中间选取三个元素，再取这三个元素的中间值作为最终的枢轴元素。或者随机从当前表中选取枢轴元素，这样做使得最坏情况在实际排序中几乎不会发生。

在最理想的状态下，也即partition（）可能做到最平衡的划分中，得到的两个子问题的大小都不可能大于n/2，在这种情况下，快速排序的运行速度将大大提升，此时，时间复杂度为O(nlog2N)。好在快速排序平均运行情况下运行时间与其最佳情况下的运行时间很接近，而不是接近最坏情况下的运行时间。

快速排序是所有内部排序算法中平均性能最优的排序算法。

稳定性：

在划分算法中，若右端区间存在两个关键字相同，且均小于基准值的记录，则在交换到左端区间后，它的相对位置会发生变化。即快速排序是一个不稳定的排序方法。

例如，L=【3,2,2】->【2,2,3】- 【2,2,3】，显然2与2的相对次序已经发生了变化。