快速排序模板

发布时间 2023-03-30 10:48:49作者: xiao王~

快排方法:

1.确定边界x
2.以x为分界点,将区间划分为:x前的数全小于x,x后的数全大于x
3.在小集合中重复上述步骤

void quick_sort(int q[] , int l , int r){
    if(l >= r) return;
    int i = l - 1 , j = r + 1;
    int x = q[l + r >> 1];
    while(i < j){
        //找到x前大于x的数,并停止
        do i ++ ; while(q[i] < x);
        //找到x后小于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);
}