快速排序

2025-05-04

Algorithm

无标签

文章目录

定义#

三路快速排序（英语：3-way Radix Quicksort）是快速排序和基数排序的混合。

过程#

三路快速排序在随机选取分界点 $m$ 后，将待排数列划分为三个部分：小于 $m$ 、等于 $m$ 以及大于 $m$ 。这样做即实现了将与分界元素相等的元素聚集在分界元素周围这一效果。

实现#

递归实现

1
template <class T>
2
void quick_sort(T arr[], const int len)
3
{
4
    if (len <= 1)
5
        return;
6

7
    const T pivot = arr[rand() % len];
8
    // i：当前下标
9
    // arr[0, j]，存储小于 pivot 的元素
10
    // arr[k, len - 1]，储大于 pivot 的元素
11
    int i = 0, j = 0, k = len;
12
    // 完成一趟三路快排，将序列分为：
13
    // 小于 pivot 的元素 | 等于 pivot 的元素 | 大于 pivot 的元素
14
    while (i < k)
15
    {
16
        if (arr[i] < pivot)
17
            swap(arr[i++], arr[j++]);
18
        else if (arr[i] > pivot)
19
            swap(arr[i], arr[k--])
20
        else
21
            i++;
22
    }
23
    // 递归完成对于两个子序列的快速排序
24
    quick_sort(arr, j);
25
    quick_sort(arr + k, len - k);
26
}

非递归实现

1
template <class T>
2
void quick_sort_non_recursive(T arr[], const int len) {
3
    if (len <= 1)
4
    return;
5

6
    // 使用栈来存储待排序的子数组的起始和结束位置
7
    stack<pair<int, int>> stk;
8
    stk.push({0, len - 1});
9

10
    while (!stk.empty()) {
11
        auto [left, right] = stk.top();
12
        stk.pop();
13

14
        if (left >= right) continue;
15

16
        // 选择基准值
17
        const T pivot = arr[left + rand() % (right - left + 1)];
18
        int i = left, j = left, k = right;
19

20
        // 三路划分
21
        while (i <= k) {
22
            if (arr[i] < pivot) {
23
                swap(arr[i++], arr[j++]);
24
            } else if (arr[i] > pivot) {
25
                swap(arr[i], arr[k--]);
26
            } else {
27
                i++;
28
            }
29
        }
30

31
        // 将子数组的边界压入栈中
32
        stk.push({left, j - 1});
33
        stk.push({k + 1, right});
34
    }
35
}