排序算法：快速排序

 1#include <iostream>
 2#include <vector>
 3#include <algorithm>
 4
 5// 统一采取 “左闭右闭” 区间
 6int partition(std::vector<int>& vec, int left, int right)
 7{
 8    // 选取一个基准值
 9    int pivot = vec[right];
10
11    int i = left;
12    // 从左往右逐个与基准值比较
13    for (int j = left; j < right; j++)
14    {
15        // 如果当前值小于等于基准值
16        // 就把更小的数(vec[j])放到前面
17        // 同时将"小数值"的区域向后扩大一位
18        if (vec[j] <= pivot)
19        {
20            std::swap(vec[i], vec[j]);
21            i++;
22        }
23    }
24
25    // 把基准值与第一个大于它的元素换位
26    // 确保 i 左边都是小于它的元素
27    // i 右边都是大于他的元素
28    std::swap(vec[i], vec[right]);
29    // 返回基准值的下标
30    return i;
31}
32void quickSort(std::vector<int>& vec, int left, int right)
33{
34    if (left < right)
35    {
36        int pivotIndex = partition(vec, left, right);
37        // 递归地对划分出来的左右区域进行排序
38        quickSort(vec, left, pivotIndex - 1);
39        quickSort(vec, pivotIndex + 1, right);
40    }
41}
42// 对外接口
43void quickSort(std::vector<int>& vec)
44{
45    quickSort(vec, 0, vec.size() - 1);
46}
47
48int main()
49{
50    std::vector<int> vec{ 9, 8, 7, 6, 5, 4, 3, 2, 1 };
51    std::ranges::for_each(vec, [](const int a) {std::cout << a << " "; });
52    std::cout << '\n';
53    quickSort(vec);
54    std::ranges::for_each(vec, [](const int a) {std::cout << a << " "; });
55}