算法基础之快速排序

快速排序

• 主要思想：分治

  • 1.确定分界点 (不一定是x)
  • 2.调整范围 左侧<=x 右侧>=x
  • 3.递归 处理左右两段

•   #include<iostream>
    using namespace std;
    const int N=1e6+10;
    int n;
    int p[N];
    void quick_sort(int p[], int l,int r){
        if(l>=r) return; 
        //即数组中没有数据 直接返回
        //也可以写成l==r
        int x=p[l+r>>1],i=l-1,j=r+1; //执行逻辑是先移动后判断 所以将ij向后移一位
        while(i<j){
            do i++ ; while(p[i]<x);  
            do j-- ; while(p[j]>x);
            if(i<j) swap(p[i],p[j]);
        }
        quick_sort(p,l,j);  //j也可以换成i-1
        quick_sort(p,j+1,r);  //j也可以换成i
        
        //不可以换成quick_sort(p,l,j-1)
        //j的位置可以保证其右侧的所有元素大于x
        //且 p[j]<=x的 所以不能将j作为右边界传入(不满足分治的要求)
    }
    int main(){
        scanf("%d", &n);  //用scanf不用cin 是因为scanf更快
        for(int i=0;i<n;i++){
            scanf("%d", &p[i]);
        }
        quick_sort(p,0,n-1);
        for(int i=0;i<n;i++){
            printf("%d", p[i]);
        }
        return 0;
    }