QuickSort 快速排序

问题

用Quick Sort对长度为 $n$ 的无序序列 $s$ 从小到大（升序）排序。

解法

在长度为 $n$ 的序列 $s = [x_0, x_1, \dots, x_{n-1}]$ 选取最左边元素 $x_0$ 作为 $pivot$ ，然后将剩余部分分为两个部分 $left = [x_1, \dots, x_k]$ 和 $right = [x_{k+1}, \dots, x_{n-1}]$ （其中 $1 \le k \le n-1$ ），满足 $left$ 所有元素都位于 $pivot$ 左边，小于等于 $pivot$ ， $right$ 所有元素都位于 $pivot$ 右边，大于等于 $pivot$ ，而 $left, right$ 内部并不必须是有序的。如图：

将 $s = [x_0, \dots, x_{n-1}]$ 中任意 $x \lt pivot$ 移动到其左边，任意 $x \gt pivot$ 移动到其右边。需要如下操作：

function Partition(s, low, high):
    let pivot = s[low]
    while low < high
        while low < high and s[high] >= pivot
            high--
        s[low] = s[high]
        while low < high and s[low] <= pivot
            low++
        s[high] = s[low]
    s[low] = pivot
    return low

(1) Partition函数第2行：令 $s$ 第一个元素 $s[low]$ 作为 $pivot$ ；

(2) Partition函数第3-9行：轮流从 $s$ 最右边选出第一个 $x \lt pivot$ 移动到其左边，从 $s$ 最左边选出第一个 $x \gt pivot$ 移动到其右边，直到 $low \ge high$ ；

(3) Partition函数第10-11行：经过移动之后 $low$ 的位置即为最终 $pivot$ 的位置，将该位置返回给函数调用者；

上述操作的示例如图：

设 $pivot = s[0] = 45, low = 0, high = n-1$ 。从 $high$ 向左搜索第一个 $s[high] = 29 \lt pivot = 45$ ，令 $s[low] = s[high]$ 。

再从 $low$ 开始向右搜索第一个 $s[low] = 90 \gt pivot = 45$ ，令 $s[high] = s[low]$ 。

再从 $high$ 向左搜索第一个 $s[high] = 13 \lt pivot = 45$ ，令 $s[low] = s[high]$ 。

上述操作直到 $low \ge high$ 停止，此时 $low$ 的位置即为 $pivot$ 的位置，令 $s[low] = pivot$ 就完成了本轮操作。

递归的对 $left$ 和 $right$ 进行该操作，即可完成整个数组排序：

function QuickSort(s, begin, end):
    if end <= begin+1
        return
    let mid = Partition(s, begin, end)
    QuickSort(s, begin, mid)
    QuickSort(s, mid+1, end)