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;  //优化之一： 选取的基准值要是首尾中三个值的中位数，所以要对数组中的三个值进行比较
        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;        //把第一个值当作 基准值
        point=a[low];
        while(low<high) {
            while(low<high&&point<=a[high]) {  //把数组右边比基准值大的值过滤了
                high--;                         
            }
            /*swap(a, low, high);*/           //优化之二：point值会频繁交换移动，所以直接赋值，将数组右边大的值填给左边小的数组
            a[low]=a[high];
            while(low<high&&a[low]<=point) {  //把数组右边比基准值大的值过滤了
                low++;
            }
            /*swap(a, low, high);*/
            a[high]=a[low];
        }
        a[low]=point;//补位，补最后那个空出来的位置
        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)  //运用尾递归，即先对数组短的进行递归，如果结束了再对point赋值 跑到另一组数组进行递归 
                { Qsort(a, low, point-1);
            
                       low=point+1;}   //执行此语句时，意味着前面一句的Qsort已经因为low等于high而终止，所以此时point+1跳出当前循环，另一对数组开始执行递归 
            
        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;
    }
}