public class InserSort {
    public static void insertSort(int a[]){
      int temp;//哨兵
      int i;//執(zhí)行趟數
      int j;
      for (i = 1; i < a.length; i++) {//執(zhí)行N-1趟
          temp=a[i];
        for ( j = i-1; (j >=0)&&(a[j]>temp); j--) {
            a[j+1]=a[j];
        }
        a[j+1]=temp;
    }
    }
    public static void main(String[] args) {
        int a[]={9,6,3,2,7,5};
        InserSort.insertSort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]);
        }
    }
}

public class BInsertSort {
/**
* 折半插入排序
* @param a
*/
    public static void BinsertSort(int a[]){
        int temp;//哨兵
        for (int i = 1; i < a.length; i++) {
            temp=a[i];
            int low=0;
            int hight=i-1;
            //查詢
            while (low<=hight) {
                int mad=(low+hight)/2;
                if (a[mad]>a[i]) {
                    hight=mad-1;
                }
                if (a[mad]<a[i]) {
                    low=mad+1;
                }
            }   
            //移動
            for (int k = i-1; k >=hight+1; k--) {
                a[k+1]=a[k];
            }
            a[hight+1]=temp;
        }
    }
    public static void main(String[] args) {
        int a[]={9,6,3,2,7,5};
        BInsertSort.BinsertSort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]);
        }
    }
}

public class ShellSort {
    /**
     * 希爾排序
     * @param a
     */
    public static void shellSort(int a[]){
        int i,j;
        int inc;//增量
        int temp;//哨兵
        for ( inc = a.length/2; inc >0; inc/=2) {//設置增量隊列
            //一趟希爾排序
            for ( i = inc; i < a.length; i++) {
                temp=a[i];
                for ( j = i; j >= inc; j-=inc) {
                    if (temp<a[j-inc]) {
                        a[j]=a[j-inc];
                    }else {
                        break;
                    }
                }
                a[j]=temp;
            }
        }
    }
    public static void main(String[] args) {
        int a[]={9,6,3,2,7,5};
        shellSort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]);
        }
    }
}

public class BubbleSort {
    /**
     * 冒泡排序
     * @param a
     */
    public static void bubbleSort(int a[]){
         int temp=0;
         int log=0;//1表示有交換 0表示沒有交換  作為結束標識
        for (int i = a.length-1; i >1; i--) {
            for (int j = 0; j < i; j++) {
                if (a[j+1]<a[j]) {
                    temp=a[j+1];
                    a[j+1]=a[j];
                    a[j]=temp;
                    log=1;
                }
            }
            if (log==0) {
                break;
            }
        }
    }
    public static void main(String[] args) {
        int a[]={2,3,5,6,7,9};
        BubbleSort.bubbleSort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]);
        }
    }
}

public class QuickSort {
    /**
     * 一趟快排序
     */
    public static int partition(int a[],int low ,int high) {
        int temp = a[low];// 支點
        while (low < high) {
            while ((low < high)&&(a[high] >= temp) ) {
                high--;
            }
            a[low]=a[high];
            while ((low < high)&&(a[low] <= temp)) {
                low++;
            }
            a[high]=a[low];
        }
        a[low]=temp;
        return low;
    }
    /**
     * 遞歸排序
     * @param a
     * @param low
     * @param high
     */
    public static void QSort(int a[],int low,int high){
        //對子序列進行排序
        if (low<high) {
            int pivot=partition(a, low , high);
            QSort(a,low, pivot-1);
            QSort(a,pivot+1,high);
        }
    }
    /**
     * 快速排序
     * @param a
     */
    public static void QuickSort(int a[]){
            QSort(a, 0, a.length-1);
    }
    //測試
    public static void main(String[] args) {
        int a[]={7,6,3,8,4,9,7};
        QuickSort.QuickSort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]);
        }
    }
}