#include <iostream>
using namespace std;
void PrintArray(int arr[],int len){
    for(int i = 0;i<len;i++){
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}

void Quicksort(int arr[],int start,int end){
    int i = start;
    int j = end;
    //基准数
    int temp = arr[start];//挖坑
    if(i<j){
        while(i<j){
            //从右向左 找比基准数小的
            while(i<j && arr[j]>=temp) {//从左往右走
                j--;
            }
            //填坑
            if(i<j){
                arr[i] = arr[j];
                i++;
            }
            //从左到右 找比基准数大的
            while(i<j && arr[i]<temp){
                i++;
            }
            //填坑
            if(i<j){
                arr[j]=arr[i];
                j--;
            }
        }
        //基准数放在合适的位置 i
        arr[i]=temp;
        //对左半部分进行快速排序
        Quicksort(arr,start,i-1);//i的位置合适，i前边都比i小
        //对右半部分进行快速排序
        Quicksort(arr,i+1,end);

    }

}