package com.ryan.demo1;

import java.lang.reflect.Array;

import javax.security.auth.kerberos.KerberosKey;

public class QuickSort {

    public static void main(String[] args) {
        int[] a= {5,2,6,0,3,9,1,7,4,8};
Qsort(a, 0, 9);
for (int i : a) {
    System.out.println(a[i]);
}
    }
    public static int partition(int[] a,int low,int high) {
        int M=low+(high-low)/2;  //優(yōu)化之一： 選取的基準(zhǔn)值要是首尾中三個(gè)值的中位數(shù)筐骇，所以要對數(shù)組中的三個(gè)值進(jìn)行比較
        if(a[low]>a[high])      //把首尾大的值換到最后面
        {swap(a,low,high);}
        if(a[M]>a[high])         //把中尾大的值換到最后面
        {swap(a,M,high);}
        if(a[low]<a[M])      //把首重大的值換到最前面
        {swap(a,M,low);}
        int point;        //把第一個(gè)值當(dāng)作 基準(zhǔn)值
        point=a[low];
        while(low<high) {
            while(low<high&&point<=a[high]) {  //把數(shù)組右邊比基準(zhǔn)值大的值過濾了
                high--;                         
            }
            /*swap(a, low, high);*/           //優(yōu)化之二：point值會(huì)頻繁交換移動(dòng)，所以直接賦值枣购，將數(shù)組右邊大的值填給左邊小的數(shù)組
            a[low]=a[high];
            while(low<high&&a[low]<=point) {  //把數(shù)組右邊比基準(zhǔn)值大的值過濾了
                low++;
            }
            /*swap(a, low, high);*/
            a[high]=a[low];
        }
        a[low]=point;//補(bǔ)位，補(bǔ)最后那個(gè)空出來的位置
        return low;
    }
    public static void Qsort(int[] a,int low,int high) {
        int point;
        int length_insertsort=7;   //插入排序的長度
        if((high-low+1)>length_insertsort) {
     while(low<high)            
        {   point=partition(a,low,high);
            if(point-low<high-point)  //運(yùn)用尾遞歸称簿，即先對數(shù)組短的進(jìn)行遞歸精堕，如果結(jié)束了再對point賦值 跑到另一組數(shù)組進(jìn)行遞歸 
                { Qsort(a, low, point-1);
            
                       low=point+1;}   //執(zhí)行此語句時(shí)，意味著前面一句的Qsort已經(jīng)因?yàn)閘ow等于high而終止瞧挤，所以此時(shí)point+1跳出當(dāng)前循環(huán)，另一對數(shù)組開始執(zhí)行遞歸 
            
        else {  Qsort(a, point+1, high);
             high=point-1;
   
        }
    }}
else{
insertSort(a,low,high);
}
}
    public static void insertSort(int[] a,int low,int high) {
                int i,j;
        for(i=low+1;i<high;i++) {
              for(j=i;(j>low)&&a[j]<a[j-1];j--) {
                    swap(a,j,j-1);
                }
            
            }
        
    }
    public static void swap(int[] a,int low,int high) {
        int temp =a[high];
        a[high]=a[low];
        a[low]=temp;
    }
}