快速排序

发表于 | 分类于

快速排序（Quick Sort），又称划分交换排序，该算法使用分治法（Divide and Conquer），将一个序列分为两个子序列。

快速排序通常明显比其他 $O(n\log n)$ 算法更快，它的内部循环可以在大部分的架构上很有效率地被实现出来。

算法描述

算法步骤为：

  1. 从数列中挑出一个数字，称为"基准"（pivot）。
  2. 重新排序数列，所有比基准值小的数字摆放在基准前面，所有比基准值大的数字摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
  3. 递归地把小于基准数字的子数列和大于基准数字的子数列排序。
  4. 递归到最底部时，数列的大小是零或一，也就是已经排序好了。

以列表 [54, 26, 93, 17, 77, 31, 44, 55, 20] 为例，快速排序运作如下：

挑选第一个数字 54 为基准数字（基准数字可以任意挑选，一般取开头或者末尾的数字）：

进行分区操作，这里采用左右两个标记（递增的leftmark 和 递减的rightmark）实现，当两者相遇时操作中止：

把基准数字放到两个子序列中间，基准数字排序完成（如图所示，54 前面的数字都比 54 小，后面的数字都比 54 大，54 所在的位置就是最终位置）：

对两个子序列分别进行排序。左序列取 31 为基准数字，右序列取 77 为基准数字，重复上述步骤直到排序完成。

Python 实现

算法的 Python 代码如下（递归法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def quicksort(var, begin, end):
    if begin < end:
        p = partition(var, begin, end)
        quicksort(var, begin, p)
        quicksort(var, p + 1, end)


def partition(var, begin, end):
    left = begin + 1
    right = end - 1
    done = False
    while not done:
        while left <= right and var[left] <= var[begin]:
            left = left + 1
        while left <= right and var[right] >= var[begin]:
            right = right - 1
        if right < left:
            done = True
        else:
            var[left], var[right] = var[right], var[left]
    var[begin], var[right] = var[right], var[begin]
    return right

a = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quicksort(a,0,9)
print(a)  # output: [17, 20, 26, 31, 44, 54, 55, 77, 93]

时间复杂度

  • 平均时间复杂度：$O(n\log n)$
  • 最坏时间复杂度：$O(n^2)$