原理

略过，网上太多了

代码

#include<iostream>
using namespace std;

const int N = 1e5 + 10;

int s[N];

void quickSort(int l, int r){
    if(l >= r) return;
    int mid = s[(l + r) >> 1];
    int i = l - 1, j = r + 1;
    while(i < j){
        do ++i; while(s[i] < mid);
        do --j; while(s[j] > mid);
        if(i < j) swap(s[i], s[j]);
    }
    quickSort(l, j);
    quickSort(j + 1, r);
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> s[i];
    quickSort(0, n - 1);
    for(int i = 0; i < n; i++) cout << s[i] << " ";
    return 0;
}

接收输入格式如下，第一行是长度，第二行是具体数字，以空格分隔

4
3 1 2 4

Q&A

1. 为什么是 do ++i; while(s[i] < mid);而不是先while

考虑如下情况

8 8 8

当队列值都相同时，i和j会停止移动，导致死循环，而先do再while会保证每轮循环指针都会移动，从而跳出循环

2. 边界必须是[l,j]和[j+1,r]吗？

也可以以l为边界，修改为[l, i-1]和[i, r]，代码如下

void quickSort(int l, int r){
    if(l >= r) return;
    int mid = s[(l + r + 1) >> 1];
    int i = l - 1, j = r + 1;
    while(i < j){
        do ++i; while(s[i] < mid);
        do --j; while(s[j] > mid);
        if(i < j) swap(s[i], s[j]);
    }
    quickSort(l, i - 1);
    quickSort(i, r);
}

2.1为什么要变成[l, i-1]和[i, r]

快排的原理是每轮执行完后，分治时，左边的都小于等于mid，而右边的都大于等于mid

i的含义是，在运行结束时，有s[l..i-1] <= mid

j的含义是，s[j+1...r] >= mid

所以s[i]是可能大于mid的，如果用[l, i]和[i+1, r]，就会出错，因为违反了定义。

2.2 为什么mid的取值方法是(l+r+1)>>1?

若没有+1，举一个错误案例

4
3 1 2 4
# 一
    l = 0, r = 3, mid = 1
    执行结束时：
    1 3 2 4， i = 1, j = 0
# 二
  l = 0, r = 0, 返回不执行
# 三
    l = 1, r = 3, mid = 2
    执行结束时：
    2 3 4， i = 2, j = 1
# 四
    l = 1, r = 1, 返回不执行
# 五
    l = 2, r = 3, mid = 3
    执行结束时：
    3 4， i = 2, j = 2
# 六
    l = 2, r = 1, 返回不执行
# 七
    l = 2, r = 3, mid = 3
    执行结束时：
    3 4， i = 2, j = 2
# 八
    l = 2, r = 1, 返回不执行

从第五轮开始了死循环，原因是递归后，左右边界没有变化(2,3)，导致无限递归

以l分割时，当mid取到s[l]，且数组有序时，i此时只会移动一次，等于l，而j会一直减到i，等于l，然后停止。此时(i,j)就是(l,r)，所以要做的就是让mid的取值不要等于s[l]，而(l+r+1)>>1是向上取整，只要l!=r，mid就永远不会取到l，保证了区间一直在改变

以r分割时也是同理，(l+r)>>1是向下取整