快速排序

  • **时间复杂度：O(nlogn)**。

  • 步骤：

    1. 确定分界点X：q[mid]。
    2. 递归处理左右两段，使得小于等于X的在数组的前面，大于等于X的在数组的后面。
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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int q[maxn];

void qs(int q[], int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1, mid = q[l + r >> 1];
    while (i < j) {
        do i++; while (q[i] < mid);
        do j--; while (q[j] > mid);
        if (i < j) swap(q[i], q[j]);
    }
    
    qs(q, l, j), qs(q, j + 1, r);
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> q[i];
    
    qs(q, 0, n - 1);
    
    for (int i = 0; i < n; i++) cout << q[i] << " ";
    return 0;
}
// -------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int q[maxn];

void qs(int q[], int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1, mid = q[l + r + 1 >> 1];
    while (i < j) {
        do i++; while (q[i] < mid);
        do j--; while (q[j] > mid);
        if (i < j) swap(q[i], q[j]);
    }
    
    qs(q, l, i - 1), qs(q, i, r);
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> q[i];
    
    qs(q, 0, n - 1);
    
    for (int i = 0; i < n; i++) cout << q[i] << " ";
    return 0;
}

不要忘记return语句。

当X取q[l+r>>1]时，qs内部函数为l,j和j+1,r。

当X取q[(l+r+1)>>1]时，qs内部函数为l,i-1和i,r。

ep：当数组为[1, 2]时，如果取X为q[l+r>>1]，qs内部函数为l,i-1和i,r，那么i为0，j为0，递归为[0, -1]，[0, 1]，无限死循环。