算法 - 快速排序

---

题目来源： https://www.acwing.com/problem/content/787/

描述：

给定你一个长度为n的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

---

快速排序是一种分而治之的一种排序方法，时间复杂度： 期望$O(nlogn)$

• 首先确定一个划分值x: 可以是最左边，最右边，中间，随机值都是可行的
• 调整范围，也叫partition过程，把小于等于x的放在左边，大于等于x的放在右边
• 递归解决左右两端

第一种划分方法，利用双指针：

• i, j 分别表示最左边和最右边
• 如果q[i] < x, i++
• 如果q[i] >= x, 判断q[j] > x:

• 如果q[j] > x, j–
• 如果q[j] <= x, 交换 q[i], q[j]的值，然后i++, j–

第一种

#include <iostream>

using namespace std;

const int N = 1e5 + 5;

int q[N];

void quickSort(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]);
    }

    quickSort(q, l, j);
    quickSort(q, j + 1, r);
}

int main() {
    int n;
    cin >> 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]);
}

第二种划分，小于x在左边，大于x在右边，等于x在中间：

• less = left - 1, more = right + 1, 指针p = left
• 如果q[p] < x: 那么less向右边扩展，然后交换值, p指针下移动
• 如果q[p] == x: p指针下移
• 如果q[p] > x: more 向左扩展，然后与指针p交换值。 #ps： 这里p指针不移动

第二种

#include <iostream>

using namespace std;

const int N = 1e5 + 5;

int q[N];

void quickSort(int q[], int l, int r) {
    if (l >= r) return;

    int p = l, less = l - 1, more = r + 1, x = q[(l + r) >> 1];
    while (p < more) {
        if (q[p] < x) swap(q[++less], q[p++]);
        else if (q[p] == x) p++;
        else swap(q[--more], q[p]);
    }

    quickSort(q, l, less);
    quickSort(q, more, r);
}


int main() {
    int n;
    cin >> 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]);
}

快排的边界条件：

• 边界条件比较难处理，比如说第一个模板代码以q[l], q[r]作为边界的时候会进入死循环, 最好的方式就是记住模板。
• 以中间点为划分点和随机划分都不会出现这种情况。