[AcWing]快速排序

代码已经在 GITHUB 开源，👉点击直达👈。

〇、算法步骤

快速排序算法本质上属于分治算法的一种：

每次排序时选取一个基准（通常选取位于数组中间的那个值效率更高）。
将小于或等于基准的数全部放到基准点的左边，将大于或等于基准的数全部放到基准的右边。
完成上一步后，会得到两个“整体上有序”的子数组。
再分别递归处理这两个子数组，直至所有元素完成排序。

一、算法模板

这里只给出其中一个模板，便于理解上述算法原理的文字内容。

/**
 * @brief 快速排序算法模板
 * @param arr 待排序数组
 * @param left 左边界索引
 * @param right 右边界索引
 */
// 递归时使用 j 作边界（推荐）
static void quick_sort(int arr[], int left, int right) {
    // 递归终止条件
    if (left >= right) { return; }

    // 初始化变量
    int x = arr[(left + right) / 2],    // 中间值，可以为 arr[left], arr[right], arr[(left + right) / 2]
        i = left - 1,                   // 左指针，初始化为数组左边界 - 1
        j = right + 1;                  // 右指正，初始化为数组右边界 + 1

    // 处理
    while (i < j) {
        do { i++; } while (arr[i] < x);     // 寻找数组左半边 >= x 的值
        do { j--; } while (arr[j] > x);     // 寻找数组右半边 <= x 的值
        if (i < j) swap(arr[i], arr[j]);    // 注意交换时指针边界
    }

    // 递归
    quick_sort(arr, left, j);           // 递归处理数组左半边（注意边界问题）
    quick_sort(arr, j + 1, right);      // 递归处理数组右半边（注意边界问题）
}