快速排序

算法思想

快速排序属于分治算法，分治算法都有三步：

1. 分成子问题
2. 递归处理子问题
3. 子问题合并

此次快速排序的模版：

• 设数组q左边界为l，右边界为r

• 第一步：确定分界点

  可以为 q[l] 或 q[(l+r)>>1]

• 第二步：调整区间（分成两端）

  l ----------------- ^ ------------------ r

  使 l 到 ^ 之间的数 <= x

  使 ^ 到 r 之间的数 >= x

  （如果与x相同在 左边还是右边都是可以的）

• 第三步：递归处理左右两端

题目

xxxxxxxxxx
给定你一个长度为n的整数数列。
​
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
​
输入格式
输入共两行，第一行包含整数 n。
​
第二行包含 n 个整数（所有整数均在1~109范围内），表示整个数列。
​
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
​
数据范围
1 ≤ n ≤ 100000
​
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5

代码实现

手打

xxxxxxxxxx
#include <cstdio>
​
const int N = 1e5 + 10;
static int q[N];
​
void QuickSort(int q[], int l, int r)
{
    // 递归的终止情况
    if (l >= r) {
        return;
    }
    
    // === 第一步：分成子问题
    int x = q[(l+r)>>1];
    // 后续实现是先移动指针再做判断，所以需要将i设为左边界-1，j设为右边界+1
    int i = l - 1;
    int j = r + 1;
    
    while (i < j) {
        // 会使得 q[l..i-1] <= x, q[i] >= x
        do {
            i++;
        } while (q[i] < x);
        // 会使得 q[j+1..r] >= x, q[j] <= x
        do {
            j--;
        } while (q[j] > x);
        // 交换，会使得 q[l..i] <= x, q[j..r] >= x
        if (i < j) {
            int tmp = q[i];
            q[i] = q[j];
            q[j] = tmp;
        }
    }
    
    // === 第二步：递归处理子问题
    // 当x=q[l], 这里不取i，否则会对相同区间无限递归。如 排序 1 2
    QuickSort(q, l, j);
    QuickSort(q, j+1, r);
    
    // === 第三步：递归处理子问题，快排这一步不需要
    
}
​
int main()
{
    int n;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &q[i]);
    }
    QuickSort(q, 0, n - 1);
    
    for (int i = 0; i < n; i++) {
        printf("%d ", q[i]);
    }
    return 0;
}

C++ STL 实现

x
#include <iostream>
#include <algorithm>
#include <cstdio>
​
using namespace std;
​
const int N = 1e5 + 10;
static int q[N];
​
int main()
{
    int n;
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &q[i]);
    }
    sort(q, q+n);
    
    for (int i = 0; i < n; i++) {
        printf("%d ", q[i]);
    }
    return 0;
}