交换排序（二）

基本概念

根据待排序列中两个元素的比较结果来交换两个元素的位置，这样的排序称为交换排序，主要包括冒泡排序和快速排序。

冒泡排序（Bubble Sort）

冒泡排序见交换排序（一）

快速排序（Quick Sort）

产生来源

Tony Hoare 爵士在 1962 年发明，被誉为“20世纪十大经典算法之一”。

基本思想

对冒泡排序的一种改进，基本思想基于分治法：

在待排序列 L[1…n] 中选取一个基准元素 pivot，通常选择第一个元素或者最后一个元素；

通过一趟排序将待排序列划分成独立的两部分 L[1…k-1] 和 L[k+1…n]，前者的元素值均比基准元素值小，而后者元素值均比基准值大；

而此时作为分割线的基准 pivot 将会落在其最终的位置上，此即为一趟快速排序；

然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

要点：递归、分治

具体做法

实现方法一：

单向遍历，对原始序列 L[p…q]，取 L[q] 为基准，设 j 为遍历指针，i 为分割线指针，即 L[p…i] 均小于 pivotkey，L[i+1…j-1] 均大于pivotkey；

起始状态时，j=p, i=p-1，两个子序列均为空，j 由低到高遍历时，如果元素大于基准，则继续向前；如果元素小于基准，则将前交换至 i+1 位置，原来 i+1 位置交换至 j，同时 ++i。

实现方法二：

双向遍历，设双指针 low 和 high，起始分别指向待排序列首尾元素，设 pivotkey 记录枢纽基准元素；

首先从 high 指针位置向前搜索，找到第一个比基准 pivotkey 小的元素并与基准元素交换，此时基准右侧元素均大于基准 pivot；

然后从 low 指针位置向后搜索，找到第一个比比基准 pivotkey 大的元素并与基准元素交换，此时基准右侧元素均小于基准 pivot；

这样一来，low 之前的元素均小于基准， high 之后元素均大于基准，重复进行这两步，当 low 和 high 重合时，基准 pivotkey 降落在最终位置上，将原序列分割成两部分，一趟快速排序完成。

代码实现

根据原理分析，快速排序的关键在于划分。

实现方法一单向遍历疗法：

// 基准枢纽 pivotkey = L[q]
// L[p...i] 均小于 pivotkey，L[i+1...j-1] 均大于pivotkey
int Partition(int L[], int p, int q)
{
    int pivotkey = L[q]; // 基准枢纽 pivotkey = L[q]
    int i = p-1, j = p; // 初始化 i=p-1, j=p 即L[p...i] = L[i+1...j-1] 均为空
    for (j; j < q; ++j) // 遍历 {p,...,q-1}
        if (L[j] <= pivotkey)
            swap(&L[++i], &L[j]); // 将小于 pivotkey 的元素移到前面
    swap(&L[i+1], &L[j]); // pivotkey 归位
    return i+1; // 返回基准值位置
}

实现方法二双向遍历疗法：

int Partition_1(int L[], int low, int high)
{
    int pivotkey = L[low]; // 选择首元素作为基准
    while(low < high)
    {
        while(low < high && L[high] >= pivotkey)
            --high;
        swap(&L[low], &L[high]);

        while(low < high && L[low] <= pivotkey)
            ++low;
        swap(&L[high], &L[low]);
    }
    return low; // 返回基准值位置，用于之后划分原序列
}

前面这种实现算法，每交换一对元素时都需要进行 3 次移动操作，但实际上，排序过程中，不断移动基准枢纽元素是没有必要的，因为只有在一趟排序结束时，即 low=high 的位置才是其最终的最值，因此不需要让基准元素参与排序过程中的交换操作，只移动与基准值相比较的元素即可。

// 升级，low=high 的位置才是最终枢纽值的位置，不需要不断移动枢纽值位置
int Partition_2(int L[], int low, int high)
{
    // 基准点的选择对快排的性能有很大影响，关系到递归栈深度，尤其是在最坏情况下
    // 起始，基准点为L[low]的值
    L[0] = L[low]; // 暂存基准点的值pivotkey，省一个变量
    while (low < high)
    {
        while(low < high && L[high] >= L[0]) --high; // 高端过滤，比它小的移动到它左侧（交换）
        L[low] = L[high]; // 直接将其移动到L[low]

        while(low < high && L[low] <= L[0]) ++low; // 低端过滤，比它大的移动到它右侧
        L[high] = L[low];
    }
    L[low] = L[0]; //基准值归位
    return low;
}

递归调用划分函数：

void QSort(int L[], int low, int high)
{
    if (low < high)
    {
        int pos = Partition(L, low, high);
        QSort(L, low, pos-1);
        QSort(L, pos+1, high);
    }
}

快速排序：

void QuickSort(int L[], int n)
{
   QSort(L, 1, n);
}

归纳分析

不稳定排序（unstable sort）

在划分算法中，若右端区间有两个关键字相同，且均小于基准值，则在交换至左端区间时，他们的相对位置会发生变化，因此，快速排序是不稳定排序。

空间复杂度

快速排序使用递归，因此需要一个递归栈来保存每层调用的必要信息，其容量应与递归调用的最大深度一致。

最好情况下，空间复杂度围为 O(log₂n)；

每一趟排序都将原序列均匀地划分为两个长度接近的子序列，则栈最大深度为 ⌈log₂(n+1)⌉。

最坏情况下，空间复杂度围为 O(n)；

每趟排序后，基准枢纽都偏向子序列的一端，需要进行 n-1 次递归调用，栈最大深度为 n。

平均情况下，快速排序的空间复杂度围为 O(log₂n)；

为改进之，可在一趟排序结束后比较两个子序列的长度，且先对较短的子序列进行快排，栈最大深度可降低至 O(log₂n)。

时间复杂度

快速排序的运行时间与划分是否对称有关，而后者又与具体使用的划分算法有关。

最好情况下，时间复杂度为 O(nlog₂n)；

划分函数尽可能的划分平衡，两边的数据量都不大于 n/2。

最坏情况下，时间复杂度为 O(n²)；

划分出的两个区域分别包含 n-1 个元素和 0 个元素，如果每一层递归均发生这种最大程度的不对称，即初始待排序列基本有序或者基本逆序。

当然可以通过随机化来改进（shuffle array 或者 randomized select pivot），使期望运行时间为 O(nlog₂n)；

平均情况下，快速排序的时间复杂度为 O(nlog₂n)；

快速排序平均情况下的运行时间与其最好情况下的运行时间很接近，而不是接近其最坏情况下的运行时间。

注意：只要 Partition 的划分比例是常数的，则快排的效率就是 O(nlog₂n)，
比如当划分比例为10000:1时（足够不平衡了），快排的效率还是 O(nlog₂n)。

文章 “A killer adversary for quicksort” 介绍了怎么样设计一个输入数组，使快排运行时间为 O(n²)。

快速排序是通常被认为在同数量级 O(nlog₂n) 的排序方法中平均性能最好的，目前被认为是最好的一种内部排序算法。

但若初始序列有序或基本有序时，快排序反而蜕化为冒泡排序，其复杂度为 O(n²)。
为改进之，通常用“三者取中法”来选取基准枢纽，即将排序区间的两个端点与中点三个记录中的中值调整为支点记录，即将其与 L[low] 交换，其余部分不变。

然而，即便如此，也不能使快速排序在初始有序时达到 O(n) 的复杂度，为此进一步修改划分算法：

在指针 --high 和 ++low 的同时进行冒泡操作，即在相邻两个记录处于“逆序”时进行交换，同时在算法中附设两个标志，分别表示 high 和 low 指针从两端向中间的移动过程中是否进行过元素交换。
如果 high 指针从高端向中间的移动过程中没有发生交换，则不需要对高端子序列进行排序；
同理，如果 low 指针从低端向中间的移动过程中没有发生交换，则不需要对低端子序列进行排序；
显然这样将进一步改善快速排序的平均性能。

初态影响

由3可知，初始有序或基本有序时会导致基准值出现严重倾向，从而影响快排的效率。
不过可采用“三值取中”或“随机取值”等方法优化基准值的选择。

过程特征

一趟排序可以确定一个元素的最终位置（基准元素），但不会产生有序子序列。

基于分治法的快速排序，依次落在其最终位置上的元素集合在算法结束前并不连续（不会产生有序子序列）。

适用性

快速排序是通常被认为在同数量级 O(nlog₂n) 的排序方法中平均性能最好的，目前被认为是最好的一种内部排序算法，只不过不稳定。

非递归

用非递归的方式实现快速排序，需用使用一个栈或者队列来保存待排序子区间的区间端点。

一次划分（快排）后可以确定一个元素的最终位置，并产生的待排子区间；
这些子区间相互独立，处理完这些子区间就完成最终排序，因此处理子区间的先后顺序并不影响最终结果

故而，用来存储区间端点的辅助栈也可以用队列代替。

算法证明（实现方法一）

对 partition 函数证明循环不变式：

A[p…i] 的所有元素小于等于 pivot，A[i+1…j-1] 的所有元素大于 pivot。

初始：i=p-1,j=p，A[p…p-1] = 空，A[p…p-1] = 空，因此成立。

保持：当循环开始前，已知 A[p…i] 的所有元素小于等于 pivot，A[i+1…j-1] 的所有元素大于pivot，

在循环体中，

如果 A[j] > pivot，那么不动，j++，此时 A[p…i] 的所有元素小于等于 pivot，A[i+1…j-1] 的所有元素大于 pivot。
如果 A[j] <= pivot，这时 A[i+1] > pivot，将 A[i+1] 和 A[j] 交换，同时 ++i，如此 A[P…i] 保持所有元素小于等于 pivot，而 A[i+1…j-1] 的所有元素大于 pivot。

终止：j = q，因此 A[p…i] 的所有元素小于等于 pivot，A[i+1…q-1] 的所有元素大于 pivot。

上篇: 交换排序（一）下篇: 插入排序（一）

基本概念
冒泡排序（Bubble Sort）
快速排序（Quick Sort）