package com.ys.sort;
 
public class InsertSort {
    public static int[] sort(int[] array){
        int j;
        //從下標為1的元素開始選擇合適的位置插入，因為下標為0的只有一個元素，默認是有序的
        for(int i = 1 ; i < array.length ; i++){
            int tmp = array[i];//記錄要插入的數(shù)據(jù)
            j = i;
            while(j > 0 && tmp < array[j-1]){//從已經(jīng)排序的序列最右邊的開始比較，找到比其小的數(shù)
                array[j] = array[j-1];//向后挪動
                j--;
            }
            array[j] = tmp;//存在比其小的數(shù)，插入
        }
        return array;
    }
         
}

//希爾排序 knuth 間隔序列 3h+1
public static void shellKnuthSort(int[] array){
    System.out.println("原數(shù)組為"+Arrays.toString(array));
    int step = 1 ;
    int len = array.length;
    while(step <= len/3){
        step = step*3 + 1;//1,4,13,40......
    }  
    while(step > 0){
        //分別對每個增量間隔進行排序
        for(int i = step ; i < len ; i++){
            int temp = array[i];
            int j = i;
            while(j > step-1 && temp <= array[j-step]){
                array[j] = array[j-step];
                j -= step;
            }
            array[j] = temp;
        }//end for
        System.out.println("間隔為"+step+"的排序結(jié)果為"+Arrays.toString(array));
        step = (step-1)/3;
    }//end while(step>0)
         
    System.out.println("最終排序："+Arrays.toString(array));
}

public static void main(String[] args) {
    int[] array = {4,2,8,9,5,7,6,1,3,10};
    shellKnuthSort(array);
}

//希爾排序 間隔序列2h
public static void shellSort(int[] array){
    System.out.println("原數(shù)組為"+Arrays.toString(array));
    int step;
    int len = array.length;
    for(step = len/2 ;step > 0 ; step /= 2){
        //分別對每個增量間隔進行排序
        for(int i = step ; i < array.length ; i++){
            int j = i;
            int temp = array[j];
            if(array[j] < array[j-step]){
                while(j-step >=0 && temp < array[j-step]){
                    array[j] = array[j-step];
                    j -= step;
                }
                array[j] = temp;
            }
        }
        System.out.println("間隔為"+step+"的排序結(jié)果為"+Arrays.toString(array));
    }
}

package com.ys.high.sort;
 
public class QuickSort {
     
    //數(shù)組array中下標為i和j位置的元素進行交換
    private static void swap(int[] array , int i , int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
     
    private static void recQuickSort(int[] array,int left,int right){
        if(right <= left){
            return;//終止遞歸
        }else{
             
            int partition = partitionIt(array,left,right);
            recQuickSort(array,left,partition-1);// 對上一輪排序(切分)時，基準元素左邊的子數(shù)組進行遞歸
            recQuickSort(array,partition+1,right);// 對上一輪排序(切分)時，基準元素右邊的子數(shù)組進行遞歸
        }
    }
     
    private static int partitionIt(int[] array,int left,int right){
        //為什么 j加一個1，而i沒有加1,是因為下面的循環(huán)判斷是從--j和++i開始的.
        //而基準元素選的array[left],即第一個元素，所以左游標從第二個元素開始比較
        int i = left;
        int j = right+1;
        int pivot = array[left];// pivot 為選取的基準元素（頭元素）
        while(true){
            while(i<right && array[++i] < pivot){}
             
            while(j > 0 && array[--j] > pivot){}
             
            if(i >= j){// 左右游標相遇時候停止， 所以跳出外部while循環(huán)
                break;
            }else{
                swap(array, i, j);// 左右游標未相遇時停止, 交換各自所指元素，循環(huán)繼續(xù)
            }
        }
        swap(array, left, j);//基準元素和游標相遇時所指元素交換，為最后一次交換
        return j;// 一趟排序完成， 返回基準元素位置(注意這里基準元素已經(jīng)交換位置了)
    }
     
    public static void sort(int[] array){
        recQuickSort(array, 0, array.length-1);
    }
     
    //測試
    public static void main(String[] args) {
        //int[] array = {7,3,5,2,9,8,6,1,4,7};
        int[] array = {9,9,8,7,6,5,4,3,2,1};
        sort(array);
        for(int i : array){
            System.out.print(i+" ");
        }
        //打印結(jié)果為：1 2 3 4 5 6 7 7 8 9
    }
}

//取數(shù)組下標第一個數(shù)、中間的數(shù)、最后一個數(shù)的中間值
private static int medianOf3(int[] array,int left,int right){
    int center = (right-left)/2+left;
    if(array[left] > array[right]){ //得到 array[left] < array[right]
        swap(array, left, right);
    }
    if(array[center] > array[right]){ //得到 array[left] array[center] < array[right]
        swap(array, center, right);
    }
    if(array[center] > array[left]){ //得到 array[center] <  array[left] < array[right]
        swap(array, center, left);
    }
     
    return array[left]; //array[left]的值已經(jīng)被換成三數(shù)中的中位數(shù)， 將其返回
}

private static int partitionIt(int[] array,int left,int right){
    //為什么 j加一個1，而i沒有加1,是因為下面的循環(huán)判斷是從--j和++i開始的.
    //而基準元素選的array[left],即第一個元素，所以左游標從第二個元素開始比較
    int i = left;
    int j = right+1;
    int pivot = array[left];// pivot 為選取的基準元素（頭元素）
     
    int size = right - left + 1;
    if(size >= 3){
        pivot = medianOf3(array, left, right); //數(shù)組范圍大于3，基準元素選擇中間值。
    }
    while(true){
        while(i<right && array[++i] < pivot){}
         
        while(j > 0 && array[--j] > pivot){}
         
        if(i >= j){// 左右游標相遇時候停止， 所以跳出外部while循環(huán)
            break;
        }else{
            swap(array, i, j);// 左右游標未相遇時停止, 交換各自所指元素，循環(huán)繼續(xù)
        }
    }
    swap(array, left, j);//基準元素和游標相遇時所指元素交換，為最后一次交換
    return j;// 一趟排序完成， 返回基準元素位置(注意這里基準元素已經(jīng)交換位置了)
}

//插入排序
private static void insertSort(int[] array){
    for(int i = 1 ; i < array.length ; i++){
        int temp = array[i];
        int j = i;
        while(j > 0 && array[j-1] > temp){
            array[j] = array[j-1];
            j--;
        }
        array[j] = temp;
    }
}

public static void testMergeSort(){
    int[] array = {4,2,9,8,1,6,3,5,7};
 
    mergeSort(array,0,array.length-1);
    System.out.println(array);
}
 
public static void mergeSort(int[] array,int left,int right){
    if(left < right){
        int mid = left + (right-left)/2;
        //對左邊數(shù)組進行排序
        mergeSort(array,left,mid);
        //對右邊數(shù)據(jù)進行排序
        mergeSort(array,mid+1,right);
        //合并兩邊數(shù)組
        merge(array,left,mid,right);
    }
}
public static void merge(int[] array,int left,int mid,int right){
    //注意每一次合并申請的臨時數(shù)組大小是不一樣的
    int[] temp = new int[right-left+1];
    //新數(shù)組的索引
    int i = 0;
    //需要合并的兩個數(shù)組起點
    int j = left,k=mid+1;
    // 把較小的數(shù)先移到新數(shù)組中
    while(j <= mid && k<=right){
        if(array[j] < array[k]){
            temp[i++] = array[j++];
        }else{
            temp[i++] = array[k++];
        }
    }
    // 把左邊剩余的數(shù)移入數(shù)組
    while(j<=mid){
        temp[i++] = array[j++];
    }
    // 把右邊邊剩余的數(shù)移入數(shù)組
    while(k<=right){
        temp[i++] = array[k++];
    }
    // 把新數(shù)組中的數(shù)覆蓋array數(shù)組
    for (int l = 0; l < temp.length; l++) {
        array[l+left] = temp[l];
    }
}