public static void bubbleSort(int[] a) {
    //臨時(shí)變量
    int temp;
    //i是循環(huán)次數(shù),也是冒泡的結(jié)果位置下標(biāo)，5個(gè)數(shù)組循環(huán)5次
    for (int i = 0; i < a.length; i++) {
      //從最后向前面兩兩對(duì)比，j是比較中下標(biāo)大的值
      for (int j = a.length - 1; j > i; j--) {
        //讓小的數(shù)字排在前面
        if (a[j] < a[j - 1]) {
          temp = a[j];
          a[j] = a[j - 1];
          a[j - 1] = temp;
        }
      }
    }
  }

public static void selectSort(int[] a) {
    //臨時(shí)變量
    int temp;
    //i是循環(huán)次數(shù),也是選擇交換的結(jié)果的位置下標(biāo)，5個(gè)數(shù)組循環(huán)5次
    for (int i = 0; i < a.length; i++) {
      //最小值下標(biāo)
      int min = i;
      for (int j = i + 1; j < a.length; j++) {
        if (a[min] > a[j]) {
          min = j;
        }
      }
      temp = a[i];
      a[i] = a[min];
      a[min] = temp;
    }
  }

public static void insertSort(int[] a) {
    int temp;
    //i是循環(huán)次數(shù),也是插入的隊(duì)列的長度，最后一位是a[i]
    //所以一開始a[0]是排好的一個(gè)隊(duì)列，比較a.length-1次，最后一次循環(huán)是a[a.length-1]插入a[0]~a[a.length-2]
    for (int i = 0; i < a.length - 1; i++) {
      //a[j]是要插入的數(shù)字，從a[j]往a[0]比較
      for (int j = i + 1; j > 0; j--) {
        //如果插入的數(shù)小，交換位置
        if (a[j] < a[j - 1]) {
          temp = a[j];
          a[j] = a[j - 1];
          a[j - 1] = temp;
        } else {
          //因?yàn)槟J(rèn)a[0]~a[i]是排好的，a[i+1]比a[i]大的話，就不用比較后面了
          break;
        }
      }
    }
  }

public static void shellSort(int[] a) {
    int temp;
    int d = a.length;
    for (; ; ) {
      d = d / 2;
      //根據(jù)差值分組為子序列
      for (int k = 0; k < d; k++) {
        //此時(shí)對(duì)每組數(shù)列進(jìn)行插入排序，數(shù)組為a[k+d],a[k+2d]...a[k+n*d]
        for (int i = k + d; i < a.length; i += d) {
          // a[j]是要插入的數(shù)字，從a[j]往a[0]比較,跨度為d
          for (int j = i; j > k; j -= d) {
            //如果插入的數(shù)小，交換位置
            if (a[j] < a[j - d]) {
              temp = a[j];
              a[j] = a[j - d];
              a[j - d] = temp;
            } else {
              //因?yàn)槟J(rèn)a[0]~a[i]是排好的，a[i+1]比a[i]大的話，就不用比較后面了
              break;
            }
          }
        }
      }
      if (d == 1) {
        break;
      }
    }
  }

public void quickSort(int a[], int l, int r) {
    //左邊必須大于右邊
    if (l >= r) {
      return;
    }
    int i = l;
    int j = r;
    //選擇第一個(gè)數(shù)為基準(zhǔn)
    int base = a[l];
    while (i < j) {
      //從右向左找第一個(gè)小于base的值，如果大于左移一位，直到找到小值或者i/j重合
      while (i < j && a[j] > base) {
        j--;
      }
      //從左向右找第一個(gè)大于base的值,如果小于右移一位，直到找到大值或者i/j重合
      while (i < j && a[i] < base) {
        i++;
      }
      //交換
      if (i < j) {
        int temp = a[j];
        a[j] = a[i];
        a[i] = temp;
      }
    }
    //將基準(zhǔn)值放到i右移到的位置
    a[i] = base;
    //將i左邊和i右邊分別排序
    quickSort(a, l, i - 1);//遞歸調(diào)用
    quickSort(a, i + 1, r);//遞歸調(diào)用
  }

private static void mergeSort(int[] a, int first, int last, int temp[]) {
    if (first < last) {
      //中間值
      int middle = (first + last) / 2;
      //左半部分排序
      mergeSort(a, first, middle, temp);
      //右半部分排序
      mergeSort(a, middle + 1, last, temp);
      //合并左右部分
      mergeArray(a, first, middle, last, temp);
    }
  }

  private static void mergeArray(int a[], int first, int middle, int end, int temp[]) {
    int i = first;
    int m = middle;
    int j = middle + 1;
    int n = end;
    int k = 0;
    while (i <= m && j <= n) {
      if (a[i] <= a[j]) {
        temp[k] = a[i];
        k++;
        i++;
      } else {
        temp[k] = a[j];
        k++;
        j++;
      }
    }
    while (i <= m) {
      temp[k] = a[i];
      k++;
      i++;
    }
    while (j <= n) {
      temp[k] = a[j];
      k++;
      j++;
    }
    for (int r = 0; r < k; r++) {
      a[first + r] = temp[r];
    }
  }

public static void heapSort(int a[]) {
    //堆頂最大值和數(shù)組最后（葉節(jié)點(diǎn)）交換 長度-1 次
    for (int i = a.length - 1; i > 0; i--) {
      //構(gòu)建大頂堆（最大堆）
      buildHeap(a, i);
      //堆頂最大值和數(shù)組最后（葉節(jié)點(diǎn)）交換
      swap(a, 0, i);
    }
  }

  //構(gòu)建大頂堆（最大堆）
  public static void buildHeap(int a[], int lastIndex) {
    //排最后的非葉節(jié)點(diǎn)為 長度/2-1，從第i檢查到堆頂?shù)?項(xiàng)，上浮大值
    for (int i = (lastIndex + 1) / 2 - 1; i >= 0; i--) {
      //必定存在的左葉節(jié)點(diǎn)，不一定存在的右葉節(jié)點(diǎn)
      int left = i * 2 + 1;
      int right = i * 2 + 2;
      //max為左右葉節(jié)點(diǎn)中的最大值
      int max = left;
      if (right <= lastIndex) {
        if (a[left] < a[right]) {
          max = right;
        }
      }
      //上浮大值
      if (a[i] < a[max]) {
        swap(a, i, max);
      }
    }
  }

  //交換值
  public static void swap(int a[], int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }

public static void radixSort(int[] a) {
    //位數(shù)
    int digit = 1;
    //作為排序后數(shù)組的新下標(biāo)
    int newIndex = 0;
    //供基數(shù)排序使用的二維數(shù)組，第一維度固定10位0~9，第二維度根據(jù)下標(biāo)依次存放每次基數(shù)排序的結(jié)果
    int[][] container = new int[10][a.length];
    //第一維度每個(gè)數(shù)組的內(nèi)容計(jì)數(shù)，最少為10，防止數(shù)組全是個(gè)位數(shù)時(shí)越界，例如五位數(shù)組最大值為8，counter.length=5 ，counter[8]就越界
    int counterLength = 10;
    if (a.length > 10) {
      counterLength = a.length;
    }
    int[] counter = new int[counterLength];
    //算出數(shù)組中最大的值，用來確定最大位
    int max = a[0];
    int maxDigit = 0;
    for (int i = 0; i < a.length; i++) {
      if (a[i] > max) {
        max = a[i];
      }
    }
    while (max > 0) {
      max /= 10;
      maxDigit++;
    }
    //對(duì)每位進(jìn)行排序
    while (digit <= maxDigit) {
      //對(duì)每個(gè)數(shù)值該位取余,container[remainder]，并計(jì)數(shù)該位置上數(shù)值的下標(biāo)counter[remainder]
      for (int num : a) {
        int remainder = (num / digit) % 10;
        container[remainder][counter[remainder]] = num;
        counter[remainder]++;
      }
      //將上一步放入容器的數(shù)值依次覆蓋到遠(yuǎn)數(shù)組中
      for (int i = 0; i < 10; i++) {
        for (int j = 0; j < counter[i]; j++) {
          a[newIndex] = container[i][j];
          newIndex++;
        }
        counter[i] = 0;
      }
      digit *= 10;
      newIndex = 0;
    }
  }