public class InsertSort {

    public static void sort(int[] arr) {
        if (arr.length >= 2) {
            for (int i = 1; i < arr.length; i++) {
                //挖出一個(gè)要用來(lái)插入的值,同時(shí)位置上留下一個(gè)可以存新的值的坑
                int x = arr[i];
                int j = i - 1;
                //在前面有一個(gè)或連續(xù)多個(gè)值比x大的時(shí)候,一直循環(huán)往前面找,將x插入到這串值前面
                while (j >= 0 && arr[j] > x) {
                    //當(dāng)arr[j]比x大的時(shí)候,將j向后移一位,正好填到坑中
                    arr[j + 1] = arr[j];
                    j--;
                }
                //將x插入到最前面
                arr[j + 1] = x;
            }
        }
    }
}

public class QuickSort {

    public static void sort(int[] arr,int begin,int end) {
        //先定義兩個(gè)參數(shù)接收排序起始值和結(jié)束值
        int a = begin;
        int b = end;
        //先判斷a是否大于b

        if (a >= b) {
            //沒必要排序
            return;
        }
        //基準(zhǔn)數(shù),默認(rèn)設(shè)置為第一個(gè)值
        int x = arr[a];

        //循環(huán)
        while (a < b) {
            //從后往前找,找到一個(gè)比基準(zhǔn)數(shù)x小的值,賦給arr[a]
            //如果a和b的邏輯正確--a<b ,并且最后一個(gè)值arr[b]>x,就一直往下找,直到找到后面的值大于x
            while (a < b && arr[b] >= x) {
                b--;
            }
            //跳出循環(huán),兩種情況,一是a和b的邏輯不對(duì)了,a>=b,這時(shí)候排序結(jié)束.二是在后面找到了比x小的值
            if (a < b) {
                //將這時(shí)候找到的arr[b]放到最前面arr[a]
                arr[a] = arr[b];
                //排序的起始位置后移一位
                a++;
            }

            //從前往后找,找到一個(gè)比基準(zhǔn)數(shù)x大的值,放在最后面arr[b]
            while (a < b && arr[a] <= x) {
                a++;
            }
            if (a < b) {
                arr[b] = arr[a];
                //排序的終止位置前移一位
                b--;
            }
        }
        //跳出循環(huán) a < b的邏輯不成立了,a==b重合了,此時(shí)將x賦值回去arr[a]
        arr[a] = x;
        //調(diào)用遞歸函數(shù),再細(xì)分再排序
        sort(arr,begin,a-1);
        sort(arr,a+1,end);
    }
}

public class MaoPao {

    public static void  sort(int[] arr){
        for (int i = 1; i < arr.length; i++) {  //第一層for循環(huán),用來(lái)控制冒泡的次數(shù)
            for (int j = 0; j < arr.length-1; j++) { //第二層for循環(huán),用來(lái)控制冒泡一層層到最后
                //如果前一個(gè)數(shù)比后一個(gè)數(shù)大,兩者調(diào)換 ,意味著泡泡向上走了一層
                if (arr[j] > arr[j+1] ){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
}

 /**
 * 終極版冒泡排序
 * 加入一個(gè)布爾變量,如果內(nèi)循環(huán)沒有交換值,說(shuō)明已經(jīng)排序完成,提前終止
 * @param arr
 */
public static void sortPlus(int[] arr){
    if(arr != null && arr.length > 1){
        for(int i = 0; i < arr.length - 1; i++){
            // 初始化一個(gè)布爾值
            boolean flag = true;
            for(int j = 0; j < arr.length - i - 1 ; j++){
                if(arr[j] > arr[j+1]){
                    // 調(diào)換
                    int temp;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    // 改變flag
                    flag = false;
                }
            }
            if(flag){
                break;
            }
        }
    }
}

public static void sort(int[] arr){
    for(int i = 0; i < arr.length - 1 ; i++){
        int min = i; // 遍歷的區(qū)間最小的值
        for (int j = i + 1; j < arr.length ;j++){
             if(arr[j] < arr[min]){
                 // 找到當(dāng)前遍歷區(qū)間最小的值的索引
                 min = j;
             }
        }
        if(min != i){
            // 發(fā)生了調(diào)換
            int temp =  arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }
}

public static void mergeSort(int[] a,int s,int e){
    int m = (s + e) / 2;
    if (s < e){
      mergeSort(a,s,m);
      mergeSort(a,m+1,e);
      //歸并
      merge(a,s,m,e);
    }
  }

  private static void merge(int[] a, int s, int m, int e) {
    //初始化一個(gè)從起始s到終止e的一個(gè)數(shù)組
    int[] temp = new int[(e - s) + 1];
    //左起始指針
    int l = s;
    //右起始指針
    int r = m+1;
    int i = 0;
    //將s-e這段數(shù)據(jù)在邏輯上一分為二,l-m為一個(gè)左邊的數(shù)組,r-e為一個(gè)右邊的數(shù)組,兩邊都是有序的
    //從兩邊的第一個(gè)指針開始遍歷,將其中小的那個(gè)值放在temp數(shù)組中
    while (l <= m && r <= e){
      if (a[l] < a[r]){
        temp[i++] = a[l++];
      }else{
        temp[i++] = a[r++];
      }
    }

    //將兩個(gè)數(shù)組剩余的數(shù)放到temp中
    while (l <= m){
      temp[i++] = a[l++];
    }
    while (r <= e){
      temp[i++] = a[r++];
    }
    
    //將temp數(shù)組覆蓋原數(shù)組
    for (int n = 0; n < temp.length; n++) {
      a[s+n] = temp[n];
    }
    
  }

/**
   * 最大頂堆排序
   * @param a
   */
  public static void topMaxHeapSort(int[] a){
    //先創(chuàng)建最大頂堆
    createTopMaxHeap(a);
    int end = a.length - 1 ;
    while(end > 0 ){
      //把0位的最大值放到最后
      swaparr(a, 0, end);
      //將計(jì)算的長(zhǎng)度減一.不考慮最后的那個(gè)值
      end--;
      //重新調(diào)整堆結(jié)構(gòu)
      handleMaxHeapFromIndex(a, end);
    }
      //打印下看看
      // System.out.println(Arrays.toString(a));
  }

  /** [3,7,1,4,9,5,6,7,2,6,8,3]
   * `````````3
   * ``````/     \
   * `````7       1
   * ````/ \     / \
   * ``4   9   5   6
   * `/ \ / \ /
   * `7 2 6 8 3
   * 變成 [9, 7, 6, 7, 6, 5, 1, 4, 2, 3, 8, 3]
   * `````````9
   * ```````/    \
   * `````7       6
   * ````/ \     / \
   * ``7   6   5   1
   * `/ \ / \ /
   * `4 2 3 8 3
   * 構(gòu)建最大頂堆, 變成父節(jié)點(diǎn)都比子節(jié)點(diǎn)大的樹
   * @param a
   */
  public static void createTopMaxHeap(int[] a){
    //從倒數(shù)第二排最后一個(gè)開始, 從下往上, 層層處理把最大的換上去構(gòu)建最大頂堆
    //如上面的注釋, 就是從5開始. 再往后就沒意義了
      handleMaxHeapFromIndex(a,a.length-1);
    //打印下看看
    // System.out.println(Arrays.toString(a));
  }

  private static void handleMaxHeapFromIndex(int[] a,int end){
    for (int i = end / 2; i>=0; i--) {
      //從i開始往后面調(diào)整它的堆
    //左子節(jié)點(diǎn), 右子節(jié)點(diǎn)
 
    // 設(shè)置一個(gè)用于玩下遍歷和判斷的子節(jié)點(diǎn), 默認(rèn)就是左邊的兒子
    int child = 2 * i + 1;
    while (child <= end){
      //如果右子節(jié)點(diǎn)比左邊大
      int leftson = child;
      int rightson = child + 1;
      if(rightson <= end && a[rightson] > a[leftson]){
        //就設(shè)置為右邊的兒子
        child++;
      }
      //再比較父子,如果兒子比父親大,就互換
      if(a[i] < a[child]){
        swaparr(a,i,child);
      }
      //繼續(xù)循環(huán)
      i = child;
      //繼續(xù)選擇它的左兒子
      child = 2 * i + 1;
    }
    }
  }

  

  private static void swaparr(int[] arr,int a,int b){
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }

 while (child <= end) {
      // 如果右子節(jié)點(diǎn)比左邊大
      int leftson = child;
      int rightson = child + 1;
      if (rightson <= end && a[rightson] > a[leftson]) {
        // 就設(shè)置為右邊的兒子
        child++;
      }
      // 再比較父子,如果兒子比父親大,就互換
      if (a[i] < a[child]) {
        swaparr(a, i, child);
      } else {
        // 否則直接跳出循環(huán), 只要父節(jié)點(diǎn)比子節(jié)點(diǎn)大, 不用管下面的調(diào)整了
        break;
      }
      // 繼續(xù)循環(huán)
      i = child;
      // 繼續(xù)選擇它的左兒子
      child = 2 * i + 1;
    
  }

 /**
   * 最大頂堆排序
   * 
   * @param a
   */
  public static void topMaxHeapSort(int[] a) {
    // 先創(chuàng)建最大頂堆
    createTopMaxHeap(a);
    System.out.println("創(chuàng)建完畢");
    int end = a.length - 1;
    while (end > 0) {
      // 把0位的最大值放到最后
      swaparr(a, 0, end);
      // 將計(jì)算的長(zhǎng)度減一.不考慮最后的那個(gè)值
      end--;
      handleMaxHeapFromIndex(a, 0, end);
    }
    // 打印下看看
    // System.out.println(Arrays.toString(a));
  }

  /** [3,7,1,4,9,5,6,7,2,6,8,3]
   * `````````3
   * ``````/     \
   * `````7       1
   * ````/ \     / \
   * ``4   9   5   6
   * `/ \ / \ /
   * `7 2 6 8 3
   * 變成 [9, 7, 6, 7, 6, 5, 1, 4, 2, 3, 8, 3]
   * `````````9
   * ```````/    \
   * `````7       6
   * ````/ \     / \
   * ``7   6   5   1
   * `/ \ / \ /
   * `4 2 3 8 3
   * 構(gòu)建最大頂堆, 變成父節(jié)點(diǎn)都比子節(jié)點(diǎn)大的樹
   * @param a
   */
  public static void createTopMaxHeap(int[] a) {
    // 從倒數(shù)第二排最后一個(gè)開始, 從下往上, 層層處理把最大的換上去構(gòu)建最大頂堆
    // 如上面的注釋, 就是從5開始. 再往后就沒意義了
    for (int i = (a.length - 1) / 2; i >= 0; i--) {
      handleMaxHeapFromIndex(a, i, a.length - 1);
    }
    // 打印下看看
    // System.out.println(Arrays.toString(a));
  }

  private static void handleMaxHeapFromIndex(int[] a, int i, int end) {
    // 從i開始往后面調(diào)整它的堆
    // 左子節(jié)點(diǎn), 右子節(jié)點(diǎn)
    // 設(shè)置一個(gè)用于玩下遍歷和判斷的子節(jié)點(diǎn), 默認(rèn)就是左邊的兒子
    int child = 2 * i + 1;
    while (child <= end) {
      // 如果右子節(jié)點(diǎn)比左邊大
      int leftson = child;
      int rightson = child + 1;
      if (rightson <= end && a[rightson] > a[leftson]) {
        // 就設(shè)置為右邊的兒子
        child++;
      }
      // 再比較父子,如果兒子比父親大,就互換
      if (a[i] < a[child]) {
        swaparr(a, i, child);
      } else {
        // 否則直接跳出循環(huán), 只要父節(jié)點(diǎn)比子節(jié)點(diǎn)大, 不用管下面的調(diào)整了
        break;
      }
      // 繼續(xù)循環(huán)
      i = child;
      // 繼續(xù)選擇它的左兒子
      child = 2 * i + 1;
    }
  }

  private static void swaparr(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }

private static void handleMaxHeapFromIndex(int[] a,int end){
 for (int i = end / 2; i>=0; i--) { //這個(gè)循環(huán)只在創(chuàng)建大頂堆的時(shí)候需要, 這個(gè)就可以去掉了
    ....
     while (child <= end){
     ...
	}
 }

private static void arraysSort(int[] a){
    Arrays.sort(a);
  }

private static void listSort(int[] a){
    List<Integer> integers = Ints.asList(a);
    Collections.sort(integers);
    integers.toArray(new Integer[a.length]);
  }

public static void main(String[] args) {

    int[] arr = new int[200000];
    int[] a =getRandomArr(arr);
    int[] b = a.clone();
    int[] c = b.clone();
    int[] d = b.clone();
    int[] e = b.clone();
    int[] f = b.clone();
    int[] g = b.clone();
    int[] h = b.clone();

    long s = Clock.systemDefaultZone().millis();
    quickSort(a, 0, a.length - 1);
    System.out.println("quickSort耗時(shí): " + (Clock.systemDefaultZone().millis() - s) + " ms");

    s = Clock.systemDefaultZone().millis();
    mergeSort(b,0,b.length-1);
    System.out.println("mergeSort: " + (Clock.systemDefaultZone().millis() - s) + " ms");

    s = Clock.systemDefaultZone().millis();
    listSort(c);
    System.out.println("listSort耗時(shí): " + (Clock.systemDefaultZone().millis() - s) + " ms");

    s = Clock.systemDefaultZone().millis();
    arraysSort(d);
    System.out.println("arraysSort耗時(shí): " + (Clock.systemDefaultZone().millis() - s) + " ms");

    s = Clock.systemDefaultZone().millis();
    maoPaoSort(e);
    System.out.println("maoPaoSort耗時(shí): " + (Clock.systemDefaultZone().millis() - s) + " ms");

    s = Clock.systemDefaultZone().millis();
    maoPaoSortPlus(f);
    System.out.println("maoPaoSortPlus耗時(shí): " + (Clock.systemDefaultZone().millis() - s) + " ms");

    s = Clock.systemDefaultZone().millis();
    insertSort(g);
    System.out.println("insertSort耗時(shí): " + (Clock.systemDefaultZone().millis() - s) + " ms");

    s = Clock.systemDefaultZone().millis();
    selectSort(h);
    System.out.println("selectSort耗時(shí): " + (Clock.systemDefaultZone().millis() - s) + " ms");



}

/**
   * 獲取一個(gè)打亂的數(shù)組
   * @param arr
   */
  private static int[] getRandomArr(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
      arr[i] = new Random().nextInt(arr.length);
    }
    return arr;
  }