AcWing 785. 快速排序

题目传送门

一、算法原理

• 每次排序时选取一个基准，将小于基准的数全部放到基准点的左边，将大于或等于基准的数全部放到基准的右边。

• 完成后，得到了两个“整体”上有序的子数组，再递归继续，直至所有元素完成排序。

二、算法模拟

假设对\(6, 1, 2, 7, 9, 3, 4, 5,10, 8\)这\(10\)个数进行排序：

本次模拟的基准是以数组的第一个元素为基准的。

从后向前扫描,\(i\)去向右找第一个大于基准\(6\)的数字,\(j\)向左查找第一个小于基准\(6\)数字：

找到\(7\)和\(5\),交换\(7\)和\(5\)

继续前进,找到\(9\)和\(4\),然后交换

\(i>=j\)，交换\(6\)和\(3\)

交换之后：\(3, 1, 2, 5, 4, 6, 9, 7, 10, 8\), 一趟排序结束。

划分的两堆数据，继续进行递归操作，完成所有数据排序。

二、实现代码

#include 

using namespace std;
const int N = 100010;
int q[N];
int n;

/**
 * 功能：利用快速排序对数组进行排序
 * @param q 要排序的数组
 * @param l 左端下标位置
 * @param r 右端下标位置
 */
void quick_sort(int q[], int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[(l + r) >> 1];
    while (i < j) {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    cin >> n;
    //读入数据
    for (int i = 1; i <= n; i++)cin >> q[i];
    //快速排序
    quick_sort(q, 1, n);
    //输出结果
    for (int i = 1; i <= n; i++) printf("%d ", q[i]);
    return 0;
}