快速排序用于对一组线性存储的数据进行排序，是实践中最常用的排序算法之一。
快速排序的核心思想是分治法（Divide and Conquer）。它通过一个称为基准（pivot）的元素来将数组分割（partition）成两个子数组。子数组中比基准小的元素放在一边，比基准大的元素放在另一边。这一过程称为分区操作。然后，递归地在两个子数组上应用同样的方法，直到数组的大小缩减到 1。
快速排序的步骤主要包括：
以下是快速排序的完整实现，使用第一个元素作为基准的分区方法：
1#include<iostream>
2#include<algorithm>
3#include<vector>
4#include "stdio.h"
5#include "time.h"
6using namespace std;
7
8int a[10000005] = {0};
9
10// 该函数用于将数组a的一个段[a[left], a[right]]按照基准值base进行划分
11int partition(int a[], int left, int right) {
12 int base = a[left]; // 选择基准值为当前段的第一个元素
13 while (left < right) {
14 // 从右向左扫描，找到第一个小于基准值的元素
15 while (left < right && a[right] >= base) {
16 right--;
17 }
18 a[left] = a[right]; // 将找到的小于基准值的元素移动到左边
19
20 // 从左向右扫描，找到第一个大于等于基准值的元素
21 while (left < right && a[left] < base) {
22 left++;
23 }
24 a[right] = a[left]; // 将找到的大于等于基准值的元素移动到右边
25 }
26 a[left] = base; // 将基准值放到最终的位置
27 return left; // 返回基准值最终的索引
28}
29
30// 快速排序函数，递归地对数组的一段进行排序
31void quick_sort(int a[], int left, int right) {
32 if (left >= right) {
33 return; // 如果当前段的长度为1或为空，则不需要排序
34 }
35 int mid = partition(a, left, right); // 对当前段进行划分，获得基准值的索引
36
37 quick_sort(a, left, mid - 1); // 递归地对基准值左边的子段进行快速排序
38 quick_sort(a, mid + 1, right); // 递归地对基准值右边的子段进行快速排序
39}
40
41int main() {
42 int n = 0;
43 cin >> n;
44 for (int i = 0; i < n; i++) {
45 cin >> a[i];
46 }
47 quick_sort(a, 0, n - 1);
48 for (int i = 0; i < n; i++) {
49 cout << a[i] << ' ';
50 }
51 cout << endl;
52 return 0;
53}以数组 [6, 3, 8, 1, 5, 2, 7, 4] 为例：
第一轮分区：partition(a, 0, 7)，选择 base = a[0] = 6
| 操作 | left | right | 数组状态 | 说明 |
|---|---|---|---|---|
| 初始 | 0 | 7 | [6, 3, 8, 1, 5, 2, 7, 4] | base=6 |
| 右→左找小于6的 | 0 | 7 | [4, 3, 8, 1, 5, 2, 7, 4] | a[7]=4<6，放到left |
| 左→右找≥6的 | 2 | 7 | [4, 3, 8, 1, 5, 2, 7, 8] | a[2]=8≥6，放到right |
| 右→左找小于6的 | 2 | 5 | [4, 3, 2, 1, 5, 2, 7, 8] | a[5]=2<6，放到left |
| 左→右找≥6的 | 4 | 5 | [4, 3, 2, 1, 5, 5, 7, 8] | left=4, a[4]=5<6继续; left=5, left==right停止 |
| 放置base | 5 | 5 | [4, 3, 2, 1, 5, 6, 7, 8] | base=6放到位置5 |
分区后：[4, 3, 2, 1, 5, 6, 7, 8]，6 在最终位置（下标5），左边都 <6，右边都 ≥6。
递归排序左半部分 [4, 3, 2, 1, 5]（下标0~4）：
递归排序右半部分 [7, 8]（下标6~7）：
最终结果：[1, 2, 3, 4, 5, 6, 7, 8]
快速排序的空间复杂度依赖于递归的深度，可以通过在代码中递归较短的子数组来优化：
稳定性：不稳定排序。相等的元素可能因分区而改变相对位置。
优点：
缺点：
使用快速排序时：
快速排序 vs 归并排序的选择：
sort() 函数，底层通常是快速排序的优化版本left < right：内层 while 循环必须始终保持 left < right 的约束，否则指针可能交叉越界。quick_sort(a, left, mid-1) 时，如果 mid=0 则 mid-1=-1，需要确保 left >= right 时直接返回。