快速排序

快速排序

八月 01, 2021

快速排序

核心思想：分治

①确定分界点：X可以取q[l],q[(l+r)>>1],q[r]
②调整范围，把小于x的放在左边，大于x的放在右边（重点）
③递归处理左右两段
方法一：

①开两个额外的数组

②q[ l~r ]

(1)q[i]<=x x->a[] (2)q[i]>x x->b[];

方法二（常用）：

①用两个指针i，j

②当i>=x 时移动j，然后找到符合条件的j，交换i，j,最后处理剩余的

1
2
3
4
5
6
7
8
9
10
11
12
void quick_sort(int q[],int l,int r){
    if(l>=r) return;
    int x=q[l];
    int i=l-1,j=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);
}