#include<iostream>
using namespace std;
void InsertSort(int* arr,int len);
void BInsertSort(int* arr,int len);//折半插入排序 
void ShellInsert(int* arr);//希尔排序 
void BubbleSort(int* arr,int len);//冒泡排序 
void QuickSort(int* arr,int low,int high);//快速排序 
int main(void){
    int arr[6]={0,9,2,1,4,5};
    //cout<<sizeof(arr)/sizeof(int);
    //InsertSort(arr,5);
    //BInsertSort(arr,5);
    //BubbleSort(arr,5);
    QuickSort(arr,1,5);
    for(int i=1;i<=5;i++) cout<<arr[i]<<" ";
    
    return 0;
}
void InsertSort(int* arr,int len){//直接插入排序 
    //使用a[0]作为哨兵
    int i,j;
    for(i=2;i<=len;i++){
        if(arr[i] < arr[i-1]){//判断下当前的数，是否比前一个小 
            arr[0] = arr[i];//复制a[i]的数值到哨兵
            for(j = i-1;arr[j] > arr[0];j--) arr[j+1] = arr[j];
            arr[j+1] = arr[0]; 
        }   
    } 
}

void BInsertSort(int *arr,int len){//折半插入排序 
    int i,j;
    for(i=2;i<=len;i++){
        arr[0] = arr[i];
        int low = 1;
        int high = i - 1;
        while(low <= high){
            int mid = (low+high)/2;
            if(arr[mid] > arr[0]) high = mid - 1;
            else low = mid + 1;
        }
        for(j=i-1;j>=high+1;j--) arr[j+1] = arr[j];//用j >= low 也是可以的 
        arr[high+1] = arr[0];
    } 
}
void BubbleSort(int* arr,int len){
    for(int i=1;i<len-1;i++){//比较的趟数
        //这里其实可以加一个flag来标记，表示若在结束前某一个没有交换，则说明此时已经达到了有序，可直接退出循环、 
        for(int j=1;j<=len-i;j++){//需要比较的元素 
            if(arr[j] > arr[j+1]){
                int t = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = t;
            }
        }
    }
}

void QuickSort(int* arr,int low,int high){//快速排序 
    if(low < high){
        int l = low;
        int h = high;
        arr[0] = arr[low];//取区间的第一个点作为pivot 
        while(l < h){//开始交换，比arr[0]的大的放在右边，小的放在arr[0]右边 
            while(l<h && arr[h] >= arr[0]) h--;//因为当前arr[low]为空，所以先从右边开始找 
            arr[l] = arr[h];
            while(l<h && arr[l] <= arr[0]) l++;
            arr[h] = arr[l];
        }
        arr[l] = arr[0];//千万不要忘记 ，将pivot放回到数组中 
        QuickSort(arr,low,h-1);//向左区间递归 
        QuickSort(arr,h+1,high);//向有区间递归 
    }
}