快速排序

贡献者： 有机物

　　 排序算法：

　　 排序算法有很多种，例如：快速排序、归并排序、插入排序、冒泡排序、堆排序等等。

　　 这里只介绍几种常用的排序算法：快速排序、归并排序和堆排序。

　　 这里先介绍快速排序：

　　 快排的主要思想是基于分治。分治的大概流程可以分为三步：分解 -> 解决 -> 合并，快排大致也是这么实现的，我们这里不详细介绍分治算法，着重讨论一下排序算法。

　　 快速排序的期望时间复杂度为 $\mathcal{O}(n \log_2 n)$，最坏时间复杂度为 $\mathcal{O}(n^2)$，因为快速排序的常数非常小，所以实际效率很高。快速排序是不稳定的。稳定的概念：如果在原序列中有两个相等的数 q[i], q[j] 且 $i < j$，排序之后，先后顺序不变，即排序之后也满足 $i < j$，说明这个排序算法是稳定的。

　　 快速排序一般分为 $3$ 步：

1. 找分界点
2. 划分区间
3. 递归处理左右两段

　　 快排与归并排序唯一一点不同的是最后不用合并，因为子数组都是原址排序的，所以不需要合并操作，数组已经有序。但归并排序的核心是合并操作。

　　 分界点一般确定为 $\dfrac{l+r}{2}$，然后维护两个指针，第一个指针从第一个位置开始走，如果指向的值如果小于分界点，那么第一个指针就继续往后走，第二个指针从最后一个位置开始往前走，如果第二个指针指向的值大于分界点，那么就继续往前走。最终使得对于分界点左边的数都 $\leq \text{mid}$，分界点右边的数都 $\geq \text{mid}$，排序成功两个指针一定会相遇，如果最后两个指针没办法再继续走下去的时候并且第一个指针在第二个指针的前面，这种情况一般是：第一个指针指向的元素大于等于分界点了，需要放到右半边、或者是第二个指针指向的元素小于等于分界点，需要放到左半边。那么就需要交换一下两个指针所指向的值，最后再递归左右两边继续做上述的操作。

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;  // 已经排好序了，直接返回
		
    int i = l - 1, j = r + 1;
    int mid = q[l + r >> 1];  // mid 为分界点
    while (i < j)
    {
        do i ++ ; while (q[i] < mid);
        do j -- ; while (q[j] > mid);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r); // 递归左右两边
    
    return;
}

　　 这里使用算法导论中的循环不变式简单的证明一下快速排序的正确性：

　　 待证问题：while 循环结束后，q[l..j] <= mid 并且 q[j + 1..r] >= mid。

　　 循环不变式：q[l...i] <= mid 并且 q[j ... r] >= mid。

　　 需要证明这个循环不变式在第一轮迭代之前是成立的，并且在每一轮迭代后也是成立的。在循环结束之后，可以证明出待证问题。

　　 证明：

• 初始化： 循环的第一轮迭代开始之前，i = l - 1, j = r + 1。所以 q[l...i] 和 q[j ... r] 都为空，循环不变式显然成立。
  
  
• 保持：需要考虑两种情况： 当对于 $i$ 指针的 $\text{do while}$ 循环结束后，有：q[l...i - 1] <= mid, q[i] >= mid。当对于 $j$ 指针的 $\text{do while}$ 循环结束后，有：q[j + 1...r] >= mid, q[j] <= mid。进行交换操作后，会使得：q[l...i] <= mid, q[j...r] >= mid。所以再下次迭代开始之前，循环不变式同样得到保持。
  
  
• 终止： 当终止时，i >= j，由于最后的一轮迭代中的 if 判断不一定执行，所以，只能得到：i >= j 和 q[l...i - 1] <= mid, q[i] >= mid 和 q[j + 1...r] >= mid, q[j] <= mid。因为有：i >= j，显然有：i - 1 >= j - 1。根据：q[l...i - 1] <= mid，q[j] <= mid 可以得到：q[l...j] <= mid。又因为 q[j + 1...r] >= mid，所以问题得证。

　　 证毕。