快速排序

快速排序有三个地方容易写错，今天终于全弄明白了。

先来看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
using namespace std;
const int N = 1e5+10;
int a[N];

void quick_sort(int l,int r){
    if(l==r) return;
    int i=l-1,j=r+1;
    int mid=a[l+r>>1];//易错点1
    while(i<j){
        while(a[--j]>mid);
        while(a[++i]<mid);
        if(i<j) //易错点2
            swap(a[i],a[j]);
    }
    quick_sort(l,j);
    quick_sort(j+1,r);//易错点3
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    quick_sort(0,n-1);
    for(int i=0;i<n;i++) cout<<a[i]<<" ";
    return 0;
}

  • 易错点1

    这里不能写成int mid=l+r>>1,这里如果记录的是下标会出错。因为后边元素交换后，a[mid]就不一定等于pivot了

  • 易错点2

    不能省略判断，i是有可能比j大的。

  • 易错点3

    考虑数组为[1,1]的情况，mid为1

    第一次循环,i停在下标0，j停在下标1，两数交换

    第二次循环，i停在下标1，j停在下标0，不满足交换条件执行递归操作。

    如果写成quick(l,i);quick(i+1,r);下标就会越界。