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移位代替除法，减少空间复杂度，时间复杂度
