快速选择(Quickselect)算法是利用快速排序(Quick Sort)算法,在排序串行的同时,选择出串行中第 K 小或是第 K 大的元素。若我们只想要从串行中找出一个第 K 小或是第 K 大元素,使用快速选择法会比使用快速排序法来得快很多,因为前者不需要把串行的排序完整做完,平均只需线性时间即可找到结果。

快速选择法(Quickselect)

快速选择法的概念

快速选择法是基于快速排序法的算法,如果您还不了解快速排序法的话,请先参考这篇文章:

使用快速选择法寻找串行中第 K 小的元素,在完成快速排序法中「把比支点元素小的元素移到支点左边和把比支点元素大的元素移到支点右边」的动作后,快速选择法并不需再对支点两端的子串行都进行排序,取而代之的是,利用此时已经固定下来的支点,可以知道支点元素是串行中第 P 小的元素,来判断 K 是否等于 P,如果 K 等于 P,我们就找到第 K 小的元素了;如果 K 不等于 P,那就只要继续用相同方式排序支点右端或是支点左端的子串行,持续下去直到找出 K 即可。

快速选择法的过程

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

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

要如何找到第 7 小的元素呢?

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

       ●
索引    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,其左边的元素正好都小于支点元素,而右边的元素正好都大于支点元素。此时索引 7 就是第 8 小的元素。由于我们要找的是第 7 小的元素,因此还要继续排序支点左边的子数组。

同样选择数组最前端的位置为支点好了,如下表所示:

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

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

       ●                      < | ◎  ◎  ◎
索引    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
       └───────────┘

支点元素被交换了之后,可以发现到支点元素被换到的位置,就是索引 6,也就是我们要找的第 7 小的位置。

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

至此我们就找出数组中第 7 小的元素是 61 了!

找出第 7 小元素后的数组

快速选择法的程序实作

与快速排序法一样,快速选择法也可以随机选择支点,而不是每次都用最左边的索引位置,避免遭遇固定的最差案例。

快速选择法的复杂度

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

项目 值 备注
最差时间复杂度 #{{O(n^2)}}# 并非要取得最大值或最小值,但选择到的支点元素刚好都是最大或最小值。
最佳时间复杂度 #{{O(n)}}# 第一次选择到的支点元素就是要找的第 K 小或是第 K 大元素。
平均时间复杂度 #{{O(n)}}#
最差空间复杂度 #{{O(1)}}#
是否稳定 否