CH1、快速排序

image.png

参数：（数组，左指针r、右指针l）

核心思想：
0、判断情况，如果左指针比右指针大，退出，否则继续
1、选中点，选指针i，左指针在初始左指针左边一个单位处，右指针j，在初始右指针右边一个单位处。
2、当（左指针比右指针小的时候）执行：
a、当比中间值小，左指针i，右边移；
b、当比中间值大，右指针j，左边移；
确保左指针比右指针小的时候，swap对应的元素。
3、分割两部分，递归调用快排
a、左部分（左指针是原左指针r，新的右指针j）
b、有部分（左指针是新左指针j+1，右指针原右指针r）

785快速排序：

#include <iostream>
using namespace std;

const int LEN=1000000+10;
  int arr[LEN];
      int n;

void quit_sort(int a[],int l,int r)
{
    if(l>=r)
        return ;   //return的作用可以减少空间复杂度
    int x=a[l+r>>1],i=l-1,j=r+1;//l+r>>1，l+r取平均值，这样降低时间复杂度。
    while(i<j)
    {
        do i++; while (a[i]<x);
        do j--; while(a[j]>x);
        if(i<j)
        {
            swap(a[i],a[j]);
        }
        
    }
    quit_sort(a,l,j);
    quit_sort(a,j+1,r);
}
int main()
{
    scanf("%d",&n);
    //int arr[n];
    
    for(int i=0;i<n;i++) scanf("%d",&arr[i]);
    
    quit_sort(arr,0,n-1);
    for(int i=0;i<n;i++) printf("%d ",arr[i]);
    return 0;
}

额外：
1、判断后return 可以减少空间复杂度
2、>>1移位代替除法，减少空间复杂度，时间复杂度