快速排序 Quicksort

什么是快速排序？

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(n log n) 次比较。在最坏状况下则需要 O(n²) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

《算法艺术与信息学竞赛》的一段描述解释了为什么在大多数情况下，快速排序都比平均时间复杂度为 O(n logn) 的排序算法表现要更好：“快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(n log n)，且 O(n log n) 记号中隐含的常数因子很小，比复杂度稳定等于 O(n log n) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。”

快速排序的过程

对一个典型的子数组 A[p..r] 进行快速排序的三步分治过程：

• 分解：数组 A[p..r] 被划分为两个（可能为空）的子数组 A[p..q-1] 和 A[q+1..r]，使得 A[p..q-1] 中的每一个元素都小于等于 A[q]，而 A[q]也小于等于 A[q+1..r] 中的每个元素。其中，计算下标 q 也是划分过程的一部分。
• 解决：通过递归调用快速排序，对子数组 A[p..q-1] 和 A[q+1..r] 进行排序。
• 合并：因为子数组都是原址排序的，所以不需要合并操作：数组 A[p..r] 已经有序。

伪代码实现如下：

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

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

正确性证明

使用循环不变式证明算法的正确性：

• 初始化：在循环的第一轮迭代开始之前，子数组中只有一个元素，显然是有序的。
• 保持：在 for 循环中，会对数组中的数据进行分割，根据分割点的值分割为两段长度几乎相等的数组，并通过交换达到有序。
• 终止：终止时，子数组都是有序的，且在之前的分割过程中，实现了每个子数组之间的有序，因此是最终有序的。

算法复杂度？

PARTITION 在子数组 A[p..r] 上的时间复杂度是 ，其中 n=r-p+1。可以看出，在最坏情况下，快速排序的每一层递归的时间复杂度是 。

如果在递归的每一层上，PARTITION 将任意常数比例的元素划分到一个子数组中，则算法的递归树深度为 ，对 PARTITION 函数稍加改变（如采用随机算法），使其在每一层上的工作量都是 O(n)，即使在最不平衡的划分情况下会增加一些新的层次，总的运行时间仍然是 O(n log n)。因此，快速排序的时间复杂度为 O(n log n)。

代码实现

Go 语言

func QuickSort(arr []int) []int {
        return _quickSort(arr, 0, len(arr)-1)
}

func _quickSort(arr []int, left, right int) []int {
        if left < right {
                partitionIndex := partition(arr, left, right)
                _quickSort(arr, left, partitionIndex-1)
                _quickSort(arr, partitionIndex+1, right)
        }
        return arr
}

func partition(arr []int, left, right int) int {
        pivot := left
        index := pivot + 1

        for i := index; i <= right; i++ {
                if arr[i] < arr[pivot] {
                        swap(arr, i, index)
                        index += 1
                }
        }
        swap(arr, pivot, index-1)
        return index - 1
}

func swap(arr []int, i, j int) {
        arr[i], arr[j] = arr[j], arr[i]
}

JavaScript

function quickSort(arr, left, right) {
    var len = arr.length,
        partitionIndex,
        left = typeof left != 'number' ? 0 : left,
        right = typeof right != 'number' ? len - 1 : right;

    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
    return arr;
}

function partition(arr, left ,right) {     // 分区操作
    var pivot = left,                      // 设定基准值（pivot）
        index = pivot + 1;
    for (var i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }        
    }
    swap(arr, pivot, index - 1);
    return index-1;
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

参考资料

• 《算法导论》第三版 第七章
• 菜鸟教程