1
#include <cmath>
2
#include <iostream>
3
using namespace std;
4
const int N = 1e5 + 5;
5
int nums[N];
6

7
// Partition 函数：将 <= x 的元素移到左边，并确保一个 x 落在最终位置
8
int Partition(int l, int r, int x) {
9
  int a = l, xi = l;
10
  for (int i = l; i <= r; i++) {
11
    if (nums[i] <= x) {
12
      swap(nums[a], nums[i]);
13
      if (nums[a] == x) { xi = a; }
14
      a++;
15
    }
16
  }
17
  swap(nums[xi], nums[a - 1]);  // 将一个 x 放到正确位置
18
  return a - 1;
19
}
20

21
void quickSort1(int l, int r) {
22
  if (l >= r) return;
23
  // 随机选择一个下标，取其值作为 pivot
24
  int rand_index = l + rand() % (r - l + 1);
25
  int x = nums[rand_index];
26
  int p = Partition(l, r, x);
27
  quickSort1(l, p - 1);
28
  quickSort1(p + 1, r);
29
}
30

31
int main() {
32
  srand(time(0));  // 初始化随机种子
33
  int n;
34
  scanf("%d", &n);
35
  for (int i = 0; i < n; i++) { scanf("%d", &nums[i]); }
36
  quickSort1(0, n - 1);
37
  for (int i = 0; i < n; i++) { printf("%d ", nums[i]); }
38
  return 0;
39
}

1
#include <cstdio>
2
#include <iostream>
3
using namespace std;
4
const int N = 1e5 + 5;
5
int nums[N];
6

7
void quickSort2(int l, int r) {
8
  if (l >= r) return;
9
  int i = l - 1, j = r + 1;
10
  // int x = nums[l + ((r - l) >> 1)];  // 取中间元素为 pivot
11
  int x = nums[l + rand() % (r - l + 1)];  // 随机选择一个下标 为 pivot (推荐)
12
  while (i < j) {
13
    do { i++; } while (nums[i] < x);
14
    do { j--; } while (nums[j] > x);
15
    if (i < j) { swap(nums[i], nums[j]); }
16
  }
17
  // 注意：Hoare 分区返回的是 j，递归 [l, j] 和 [j+1, r]
18
  quickSort2(l, j);
19
  quickSort2(j + 1, r);
20
}
21

22
int main() {
23
  int n;
24
  scanf("%d", &n);
25
  for (int i = 0; i < n; i++) { scanf("%d", &nums[i]); }
26
  quickSort2(0, n - 1);
27
  for (int i = 0; i < n; i++) { printf("%d ", nums[i]); }
28
  return 0;
29
}

1
#include <cstdio>
2
#include <iostream>
3
using namespace std;
4

5
const int N = 1e5 + 5;
6
int nums[N];
7

8
void quickSort3(int l, int r) {
9
  if (l >= r) return;
10
  // int x = nums[l + ((r - l) >> 1)];  // pivot 值
11
  int x = nums[l + rand() % (r - l + 1)];  // 随机生成位置取 pivot 值（推荐）
12
  int lt = l;                        // [l, lt-1] 为 < x 的区域
13
  int gt = r;                        // [gt+1, r] 为 > x 的区域
14
  int i = l;                         // 当前扫描指针
15

16
  while (i <= gt) {
17
    if (nums[i] < x) {
18
      swap(nums[i], nums[lt]);
19
      lt++;
20
      i++;
21
    } else if (nums[i] > x) {
22
      swap(nums[i], nums[gt]);
23
      gt--;
24
      // 注意：此处 i 不自增，因为从 gt 换来的元素未被检查
25
    } else {
26
      i++;  // 等于 x，直接跳过
27
    }
28
  }
29

30
  // 递归处理 < x 和 > x 的部分，== x 的部分已就位
31
  quickSort3(l, lt - 1);
32
  quickSort3(gt + 1, r);
33
}
34

35
int main() {
36
  int n;
37
  scanf("%d", &n);
38
  for (int i = 0; i < n; i++) { scanf("%d", &nums[i]); }
39
  quickSort3(0, n - 1);
40
  for (int i = 0; i < n; i++) { printf("%d ", nums[i]); }
41
  return 0;
42
}