快速排序(Quick Sort)算法又称为划分交换排序(Partition-Exchange Sort)算法,是实用性很高的排序算法,它可以在 O(nlogn) 的时间复杂度完成排序,虽然是不稳定排序,但它的速度完全可以弥补这个缺点。

快速排序法(Quick Sort)

快速排序法的概念

大致上来说,快速排序法就是先在串行中找出一个元素作为支点(pivot),然后想办法将比支点小的元素移动到支点元素的左边,比支点大的元素移动到支点元素的右边,接着再用同样的方法继续对支点的左边子数组和右边子数组进行排序。

快速排序法的过程

假设现在有个数组数据,内容如下:

索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79

要如何将它递增排列呢?

一开始当然要先选择一个支点。在此就选择数组最前端的位置为支点好了,如下表所示:

       ●
索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79

接着从最尾端开始,往前寻找比支点元素还要小的元素。可以找到索引 8 的元素 32,比支点元素 69 还要小。如下表所示:

       ●                              <
索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79

接着从除了支点的最左端开始,寻找比支点元素还要更大的元素。可以找到索引 1 的元素 81,比支点元素 69 还要大。如下表所示:

       ●  >                          <
索引    0   1   2   3   4   5   6   7   8   9
数值   69  81  30  38   9   2  47  61  32  79

若此时比支点元素更大的元素位置小于比支点元素更小的元素位置(换句话说就是,比支点元素更大的元素在比支点元素更小的元素左边),则交换两个元素的位置,如下表所示:

       ●  >                          <
索引    0   1   2   3   4   5   6   7   8   9
数值   69  32  30  38   9   2  47  61  81  79
           └─────────────┘

接着从原先比支点元素更小的元素位置继续向左寻找比支点元素更小的元素。可以找到索引 7 的元素 61,比支点元素 69 还要小。如下表所示:

       ●  >                      <
索引    0   1   2   3   4   5   6   7   8   9
数值   69  32  30  38   9   2  47  61  81  79

因为索引 7 还在原先比支点元素更大的元素位置之右边,因此再继续从原先比支点元素更大的元素位置,向右寻找比支点元素更大的元素。可以找到索引 8 的元素 81,比支点元素 69 还要大。如下表所示:

       ●                          <  >
索引    0   1   2   3   4   5   6   7   8   9
数值   69  32  30  38   9   2  47  61  81  79

此时比支点元素更大的元素位置大于比支点元素更小的元素位置(换句话说就是,比支点元素更大的元素在比支点元素更小的元素右边),则将比支点元素更小的元素与支点元素交换,如下表所示:

       ●                          <  >
索引    0   1   2   3   4   5   6   7   8   9
数值   61  32  30  38   9   2  47  69  81  79
       └─────────────┘

                                   ○
索引    0   1   2   3   4   5   6   7   8   9
数值   61  32  30  38   9   2  47  69  81  79

支点元素被交换了之后,可以发现支点元素被换到的位置,也就是索引 7,其左边的元素正好都小于支点元素,而右边的元素正好都大于支点元素。

接下来再针对支点元素左边的子数组和支点右边的子数组进行排序,排序过程如下:

       ●                         | ○
索引    0   1   2   3   4   5   6 |  7   8   9
数值   61  32  30  38   9   2  47 | 69  81  79

       ●                      < | ○
索引    0   1   2   3   4   5   6 |  7   8   9
数值   61  32  30  38   9   2  47 | 69  81  79

       ●                      <  > | ○
索引    0   1   2   3   4   5   6     |  7   8   9
数值   61  32  30  38   9   2  47     | 69  81  79

       ●                      <  > | ○
索引    0   1   2   3   4   5   6     |  7   8   9
数值   47  32  30  38   9   2  61     | 69  81  79
       └───────────┘

                               ○ | ○
索引    0   1   2   3   4   5   6 |  7   8   9
数值   47  32  30  38   9   2  61 | 69  81  79

       ●                     | ○ | ○
索引    0   1   2   3   4   5 |  6 |  7   8   9
数值   47  32  30  38   9   2 | 61 | 69  81  79

       ●                  < | ○ | ○
索引    0   1   2   3   4   5 |  6 |  7   8   9
数值   47  32  30  38   9   2 | 61 | 69  81  79

       ●                  <  > | ○ | ○
索引    0   1   2   3   4   5     |  6 |  7   8   9
数值   47  32  30  38   9   2     | 61 | 69  81  79

       ●                  <  > | ○ | ○
索引    0   1   2   3   4   5     |  6 |  7   8   9
数值    2  32  30  38   9  47     | 61 | 69  81  79
       └─────────┘

                           ○ | ○ | ○
索引    0   1   2   3   4   5 |  6 |  7   8   9
数值    2  32  30  38   9  47 | 61 | 69  81  79

       ●                 | ○ | ○ | ○
索引    0   1   2   3   4 |  5 |  6 |  7   8   9
数值    2  32  30  38   9 | 47 | 61 | 69  81  79

       <                 | ○ | ○ | ○
索引    0   1   2   3   4 |  5 |  6 |  7   8   9
数值    2  32  30  38   9 | 47 | 61 | 69  81  79

       ○                 | ○ | ○ | ○
索引    0   1   2   3   4 |  5 |  6 |  7   8   9
数值    2  32  30  38   9 | 47 | 61 | 69  81  79

       ○ | ●             | ○ | ○ | ○
索引    0 |  1   2   3   4 |  5 |  6 |  7   8   9
数值    2 | 32  30  38   9 | 47 | 61 | 69  81  79

       ○ | ●          < | ○ | ○ | ○
索引    0 |  1   2   3   4 |  5 |  6 |  7   8   9
数值    2 | 32  30  38   9 | 47 | 61 | 69  81  79

       ○ | ●      >  < | ○ | ○ | ○
索引    0 |  1   2   3   4 |  5 |  6 |  7   8   9
数值    2 | 32  30  38   9 | 47 | 61 | 69  81  79

       ○ | ●      >  < | ○ | ○ | ○
索引    0 |  1   2   3   4 |  5 |  6 |  7   8   9
数值    2 | 32  30   9  38 | 47 | 61 | 69  81  79
                    └─┘

       ○ | ●      <  > | ○ | ○ | ○
索引    0 |  1   2   3   4 |  5 |  6 |  7   8   9
数值    2 | 32  30   9  38 | 47 | 61 | 69  81  79

       ○ | ●      <  > | ○ | ○ | ○
索引    0 |  1   2   3   4 |  5 |  6 |  7   8   9
数值    2 |  9  30  32  38 | 47 | 61 | 69  81  79
            └───┘

       ○ |         ○     | ○ | ○ | ○
索引    0 |  1   2   3   4 |  5 |  6 |  7   8   9
数值    2 |  9  30  32  38 | 47 | 61 | 69  81  79

       ○ | ●     | ○     | ○ | ○ | ○
索引    0 |  1   2 |  3   4 |  5 |  6 |  7   8   9
数值    2 |  9  30 | 32  38 | 47 | 61 | 69  81  79

       ○ | <     | ○     | ○ | ○ | ○
索引    0 |  1   2 |  3   4 |  5 |  6 |  7   8   9
数值    2 |  9  30 | 32  38 | 47 | 61 | 69  81  79

       ○ | ○     | ○     | ○ | ○ | ○
索引    0 |  1   2 |  3   4 |  5 |  6 |  7   8   9
数值    2 |  9  30 | 32  38 | 47 | 61 | 69  81  79

       ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ●
索引    0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8   9
数值    2 |  9 | 30 | 32 | 38 | 47 | 61 | 69 | 81  79

       ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ●  <
索引    0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8   9
数值    2 |  9 | 30 | 32 | 38 | 47 | 61 | 69 | 81  79

       ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ●  <  >
索引    0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8   9
数值    2 |  9 | 30 | 32 | 38 | 47 | 61 | 69 | 81  79

       ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ●  <  >
索引    0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8   9
数值    2 |  9 | 30 | 32 | 38 | 47 | 61 | 69 | 79  81
                                               └─┘

       ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ |     ○
索引    0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8   9
数值    2 |  9 | 30 | 32 | 38 | 47 | 61 | 69 | 79  81

       ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○ | ○
索引    0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9
数值    2 |  9 | 30 | 32 | 38 | 47 | 61 | 69 | 79 | 81

快速排序法的排序过程动画

快速排序法的程序实作

在实作程序的时候,应该要避免使用递归(Recursive)的结构,因为递归需要不断地重新建构函数的堆栈空间,硬件资源的负担会比较大,且若是递归层数过多还会导致堆栈溢出(Stack Overflow)。所以比较好的做法还是在一个函数内以循环迭代的方式来完成。

由于快速排序法本身就是一种原地(in-place)算法的关系,因此也很容易转换成迭代的结构来实作,只需要多加一个堆栈结构(可以直接用数组)来模拟函数的堆栈空间即可。

为了避免遭遇固定的最差案例,支点的选择不应该每次都用最左边的索引位置,随机选择会比较保险。

实务上使用快速排序法时,常会去检查子串行的大小是否过长,如果子串行长度不长(10 个元素左右),会使用适合拿来排序少量数据的插入排序等算法来完成排序。

快速排序法的复杂度

以 #{{n}}# 来表示要排序的数据笔数。

项目 值 备注
最差时间复杂度 #{{O(n^2)}}# 选择到的支点元素刚好都是最大或最小值。
最佳时间复杂度 #{{O(n \log n)}}# 选择到的支点元素刚好都是中间值。
平均时间复杂度 #{{O(n \log n)}}#
最差空间复杂度 #{{O(n)}}#
是否稳定 否