Leto的博客
0%

快速排序与快速选择

发表于 更新于 Valine：

快速排序与快速选择

快速排序

本文中的快速排序算法来自于 YouTube 视频：Quicksort 。

中心思想

快速排序的思想是分而治之。随机选取一个元素 pivot，然后对数据进行原地重排，使得数据变为如下形式：pivot 左侧元素均比 pivot 小，右侧元素均比它大。然后分别对左右两侧的元素进行该操作，不断递归。

通常选取数组最后一个元素作为 pivot，但是最坏情况的时间复杂度会达到 O(n2)，优化方法是随机选取 pivot 后与最后的元素进行交换。

算法流程

对于长度为 n - 1 的数组，定义以下三个值。

pivot：位于 n - 1 的元素（序列最后一个元素），是进行数组分割的中间值。

spliter：是最终分割序列的元素位置，从 0 开始。每次发现位于 current 的元素小于 pivot 时向后移动 1；完成一次排序扫描后，将 pivot 元素交换至 spliter 位置，分别对其分割出的前后元素序列进行递归排序。

current：当前进行比较的元素位置，从 0 开始，在循环中向后不断移动。每次循环中此元素与 pivot 比较，如果小于 pivot 则与 spliter 位置的元素进行交换。最后在 pivot 前停止。

开始时 spliter = current = 0，arr[current] = 5 < pivot = 6，交换 arr[spliter] 与 arr[current]，实际上没有发生交换；spliter++。

现在 spliter = current = 1，arr[current] = 2 < pivot = 6，交换，spliter++。

过程同上。

此时 spliter = current = 3，arr[current] = 7 > pivot = 6，不进行交换。

此时 spliter = 3，current = 4，arr[current] = 3 < pivot = 6，需要交换 arr[current] 与 arr[spliter]，并且 spliter++。

交换完成后 spliter = current = 4。此时 current 元素位于 pivot 之前一位，循环结束。需要将 arr[current] 与 pivot 元素进行交换。

交换完成后，本次 quickSort 函数调用结束。

本次函数运行的结果：pivot 位于两端序列中间，前面的序列元素均比 pivot 小，后面的序列元素均比 pivot 大。此时分别对这两段序列运行 quickSort 函数。

前一段的子序列排序完成后，序列再次被位于 spliter 位置的 pivot 分开，再次对前后两个序列进行分别递归。

对于长度为 0 或 1 的序列，需要进行额外判断，以防止递归出错。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <typename T>
void quickSort(T *t, int n)
{
    if (n <= 1)
    {
        return;
    }
    int split = 0;
    for (int i = 0; i < n - 1; i++)
    {
        if (t[i] < t[n - 1])
        {
            swap(t[i], t[split]);
            split++;
        }
    }
    swap(t[split], t[n - 1]);
    quickSort(t, split);
    quickSort(t + split + 1, n - split - 1);
}

快速选择

快速选择是一种从序列中选取大小为第 n 位的元素的方法。快速排序和快速选择都是 C. A. R. Hoare （东尼霍尔）提出的，二者也有相似之处。

快速选择的总体思路与快速排序一致，选择一个元素作为基准来对元素进行分区，将小于和大于基准的元素分在基准左边和右边的两个区域。不同的是，快速选择并不递归访问双边，而是只递归进入一边的元素中继续寻找。这降低了平均时间复杂度，从O(nlogn)至O(n)，不过最坏情况仍然是O(n2)。

以上引自维基百科。

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
27
28
29
30
31
32
33
template <class T>
T quickSelect(T *t, int n, int idx, int des)
{
    if (n <= 1)
    {
        if (idx + n == des)
        {
            return *(t + n);
        }
    }
    int split = 0;
    for (int i = 0; i < n - 1; i++)
    {
        if (t[i] < t[n - 1])
        {
            swap(t[i], t[split]);
            split++;
        }
    }
    swap(t[split], t[n - 1]);
    if (idx + split == des)
    {
        return *(t + split);
    }
    else if (idx + split > des)
    {
        return quickSelect(t, split, idx, des);
    }
    else
    {
        return quickSelect(t + split + 1, n - split - 1, idx + split + 1, des);
    }
}