快速排序

        
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

        #include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 5;
int a[maxn];
int n;

void quick_sort(int l, int r) {
    // 1. 递归出口：如果区间只有一个数或没有数，直接返回
    if (l >= r) return;

    // 2. 选取基准数 (Pivot)
    // 建议取中间的数，防止在原本有序的数组上退化成 O(N^2)
    int mid = a[(l + r) / 2];
    
    // 定义双指针
    int i = l, j = r;

    // 3. Partition 分区操作
    // 目标：让左边 [l, j] 所有的数 <= mid
    //       让右边 [i, r] 所有的数 >= mid
    while (i <= j) {
        
        // 左指针向右找，直到找到一个 >= mid 的数停下
        // 注意：这里必须是 < mid，不能是 <=。遇到等于 mid 的也要停下，
        // 这样可以将重复的 mid 均匀分散到两边，避免树倾斜。
        while (a[i] < mid) i++;

        // 右指针向左找，直到找到一个 <= mid 的数停下
        while (a[j] > mid) j--;

        // 如果指针没有交错，说明找到了一对“放错位置”的数，交换它们
        if (i <= j) {
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }

    // 4. 递归处理子区间
    // 此时指针已经“错车”了：j 在左边，i 在右边 (j < i)
    // 分割点变成了 j 和 i
    
    // 递归处理左半段 [l ... j]
    if (l < j) quick_sort(l, j);
    
    // 递归处理右半段 [i ... r]
    if (i < r) quick_sort(i, r);
}

int main() {
    // 读写加速
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    quick_sort(1, n);

    for (int i = 1; i <= n; ++i) cout << a[i] << " ";
    cout << endl;

    return 0;
}
    

        
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

        #include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6+5;
int a[maxn];
int n;

// 三路快速排序 3-Way Quick Sort
void quick_sort(int l, int r) {
    if (l >= r) return;

    // 1. 随机选一个基准数 (防止被针对卡成 O(N^2))
    // 也可以简单写成 int key = a[(l+r)/2];
    int rand_idx = l + rand() % (r - l + 1);
    swap(a[l], a[rand_idx]); 
    int key = a[l]; // 选取 a[l] 作为 key，并以此展开

    // 2. 定义指针
    int lt = l;     // lt (less than) : 指向 "等于区" 的第一个位置
    int gt = r;     // gt (greater than): 指向 "等于区" 的最后一个位置
    int i = l + 1;  // i : 当前扫描到的位置 (从 l+1 开始，因为 a[l] 是 key)

    // 3. 扫描并分类
    while (i <= gt) {
        if (a[i] < key) {
            // 情况A: 发现比 key 小的，扔到左边 (lt)
            // 把 a[i] 和 a[lt] 交换，然后 lt 和 i 都右移
            swap(a[i], a[lt]);
            lt++;
            i++;
        } 
        else if (a[i] > key) {
            // 情况B: 发现比 key 大的，扔到右边 (gt)
            // 把 a[i] 和 a[gt] 交换，gt 左移
            // 注意：i 不能动！因为从 gt 换回来的数还没检查过
            swap(a[i], a[gt]);
            gt--;
        } 
        else {
            // 情况C: 等于 key，直接跳过，i 右移
            i++;
        }
    }

    // 此时数组状态：
    // [l ... lt-1] 都是 < key
    // [lt ... gt]  都是 == key (这一段已经排好了，不需要递归！)
    // [gt+1 ... r] 都是 > key

    // 4. 递归处理左右两边
    quick_sort(l, lt - 1);
    quick_sort(gt + 1, r);
}

int main() {
    // 基础输入输出优化
    ios::sync_with_stdio(false); cin.tie(0);
    
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];

    // 种子随机数，防止被黑客数据卡死
    srand(time(0)); 
    
    quick_sort(1, n);

    for(int i = 1; i <= n; ++i) cout << a[i] << (i == n ? "" : " ");
    cout << "\n";

    return 0;
}