排序筆記

/**
 * @author: shihchieh.ma
 * @create: 2020/6/15 6:13 下午
 * @email: shihchieh.ma@gail.com
 * @description:
 */
public class Sort {

  public static final int[] INTS = {
    //        24, 352, 23, 4, 1, 421, 5, 6, 436, 7, 86, 97, 9, 74, 34, 234, 1, 3, 6, 7
    10, 8, 6, 4, 2
  };

/**
   * @param n 生成n個(gè)元素的隨機(jī)數(shù)組
   * @param rangeL 隨機(jī)范圍[rangeL
   * @param rangeR rangeR]
   * @return 返回一個(gè)隨機(jī) int 型數(shù)組
   */
  public static int[] gennerateArray(int n, int rangeL, int rangeR) {
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = (int) (Math.random() * (rangeR - rangeL + 1)) + rangeL;
    }
    return arr;
  }

  public static void main(String[] args) {
    //    int[] INTS = gennerateArray(1000, 10);
    long startTime, endTime;
    //    冒泡排序
    int[] bubbleArr = INTS.clone();
    startTime = System.currentTimeMillis();
    bubbleSort(bubbleArr);
    endTime = System.currentTimeMillis();
    printArray("冒泡排序:", bubbleArr, endTime - startTime);

    //    選擇排序
    int[] selectionArr = INTS.clone();
    startTime = System.currentTimeMillis();
    selectionSort(selectionArr);
    endTime = System.currentTimeMillis();
    printArray("選擇排序:", selectionArr, endTime - startTime);

    //    插入排序
    int[] insertArr = INTS.clone();
    startTime = System.currentTimeMillis();
    insertSort(insertArr);
    endTime = System.currentTimeMillis();
    printArray("插入排序:", insertArr, endTime - startTime);

    //    快速排序
    int[] quickArr = INTS.clone();
    startTime = System.currentTimeMillis();
    quickSort(quickArr, 0, quickArr.length - 1);
    endTime = System.currentTimeMillis();
    printArray("快速排序:", quickArr, endTime - startTime);

    //    計(jì)數(shù)排序
    int[] countArr = INTS.clone();
    startTime = System.currentTimeMillis();
    int[] countSort = countSort(countArr);
    endTime = System.currentTimeMillis();
    printArray("計(jì)數(shù)排序:", countSort, endTime - startTime);

    //    基數(shù)排序
    int[] radixArr = INTS.clone();
    startTime = System.currentTimeMillis();
    radixSort(radixArr);
    endTime = System.currentTimeMillis();
    printArray("基數(shù)排序:", radixArr, endTime - startTime);

    // 桶排序
    int[] bucketArr = INTS.clone();
    startTime = System.currentTimeMillis();
    int[] bucketSort = bucketSort(bucketArr);
    endTime = System.currentTimeMillis();
    printArray("桶排序:", bucketSort, endTime - startTime);

    // 歸并排序
    int[] mergeArr = INTS.clone();
    startTime = System.currentTimeMillis();
    mergeSort(mergeArr, 0, mergeArr.length - 1, new int[mergeArr.length]);
    endTime = System.currentTimeMillis();
    printArray("歸并排序:", mergeArr, endTime - startTime);

    // 希爾排序
    int[] shellArr = INTS.clone();
    startTime = System.currentTimeMillis();
    shellSort(shellArr);
    endTime = System.currentTimeMillis();
    printArray("希爾排序:", shellArr, endTime - startTime);

    // 堆排序
    int[] heapArr = INTS.clone();
    startTime = System.currentTimeMillis();
    heapSort(heapArr);
    endTime = System.currentTimeMillis();
    printArray("堆排序:", heapArr, endTime - startTime);
  }

  private static void printArray(String name, int[] ints, long time) {
    for (int anInt : ints) {
      System.out.print("_" + anInt + "_");
    }
    System.out.println("\t");
    System.out.println(name + "耗時(shí):" + time);
    System.out.println();
  }
}

冒泡排序

  1. 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
  2. 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。
  3. 針對所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
  4. 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
  /** 冒泡排序 */
  private static void bubbleSort(int[] clone) {
    for (int i = 0, j = clone.length; i < j; i++) {
      for (int k = 0, l = j - 1 - i; k < l; k++) {
        if (clone[k] > clone[k + 1]) {
          clone[k] = clone[k] ^ clone[k + 1];
          clone[k + 1] = clone[k] ^ clone[k + 1];
          clone[k] = clone[k] ^ clone[k + 1];
        }
      }
    }
  }

選擇排序

  1. 在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?/li>
  2. 從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?/li>
  3. 以此類推，直到所有元素均排序完畢
  /** 選擇排序 */
  private static void selectionSort(int[] clone) {
    for (int i = 0, j = clone.length; i < j; i++) {
      int minIndex = i;
      for (int k = i; k < j; k++) {
        if (clone[k] < clone[minIndex]) {
          minIndex = k;
        }
      }
      if (minIndex != i) {
        clone[i] = clone[i] + clone[minIndex];
        clone[minIndex] = clone[i] - clone[minIndex];
        clone[i] = clone[i] - clone[minIndex];
      }
    }
  }

插入排序

  1. 第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序
  2. 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
  3. 如果該元素（已排序）大于新元素，將該元素移到下一位置
  4. 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
  5. 將新元素插入到該位置后
  6. 重復(fù)步驟 2->5
  /** 插入排序 */
  private static void insertSort(int[] clone) {
    for (int i = 1, j = clone.length; i < j; i++) {
      int k = i;
      int temp = clone[k];
      while (k > 0 && clone[k - 1] > temp) {
        clone[k] = clone[k - 1];
        k--;
      }
      clone[k] = temp;
    }
  }

快速排序

  1. 選取第一個(gè)數(shù)為基準(zhǔn)
  2. 將比基準(zhǔn)小的數(shù)交換到前面，比基準(zhǔn)大的數(shù)交換到后面
  3. 對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)
  /**
   * 快速排序
   *
   * @param clone 數(shù)組
   * @param leftIndex 左邊角標(biāo) 初始0
   * @param rightIndex 右邊角標(biāo) 初始length-1
   */
  private static void quickSort(int[] clone, int leftIndex, int rightIndex) {
    // temp-基準(zhǔn)位
    int i, j, temp;
    if (leftIndex > rightIndex) {
      return;
    }
    i = leftIndex;
    j = rightIndex;
    temp = clone[leftIndex];
    while (i < j) {
      // 先右邊，往左遞減,找一個(gè)小于基準(zhǔn)位的數(shù)
      // 當(dāng)右邊的角標(biāo)位置所在的數(shù)>基準(zhǔn)位的數(shù)時(shí)，繼續(xù)從右往左找（同時(shí) j 索引-1)
      // 找到就跳出 while循環(huán)
      while (temp <= clone[j] && i < j) {
        j--;
      }
      // 再左邊，往右遞增
      // 如上
      while (temp >= clone[i] && i < j) {
        i++;
      }
      // 滿足條件則交換
      if (i < j) {
        clone[i] = clone[i] + clone[j];
        clone[j] = clone[i] - clone[j];
        clone[i] = clone[i] - clone[j];
      }
    }
    // i=j 左右在同一位置
    // 最后將基準(zhǔn)為與i和j相等位置的數(shù)字交換
    clone[leftIndex] = clone[i];
    clone[i] = temp;
    // 左半數(shù)組<(i或j所在索引的數(shù))<右半數(shù)組
    // 也就是說(i或j所在索引的數(shù))已經(jīng)確定排序位置，就不用再排序了，
    // 相同的方法分別處理左右數(shù)組
    // 遞歸調(diào)用左半數(shù)組
    quickSort(clone, leftIndex, j - 1);
    // 遞歸調(diào)用右半數(shù)組
    quickSort(clone, j + 1, rightIndex);
  }

計(jì)數(shù)排序

  1. 找出待排序的數(shù)組中最大和最小的元素；
  2. 統(tǒng)計(jì)數(shù)組中每個(gè)值為 i 的元素出現(xiàn)的次數(shù)，存入數(shù)組 C 的第 i 項(xiàng)；
  3. 對所有的計(jì)數(shù)累加（從 C 中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加）；
  4. 向填充目標(biāo)數(shù)組：將每個(gè)元素 i 放在新數(shù)組的第 C[i] 項(xiàng)，每放一個(gè)元素就將 C[i] 減去 1；

當(dāng)數(shù)組最大和最小差值過大時(shí)，不適合計(jì)數(shù)排序
當(dāng)數(shù)組元素不是整數(shù)時(shí)，不適合用計(jì)數(shù)排序

  /** 計(jì)數(shù)排序 */
  private static int[] countSort(int[] clone) {
    int max = clone[0];
    int min = clone[0];
    for (int i = 1, j = clone.length; i < j; i++) {
      if (clone[i] > max) {
        max = clone[i];
      }
      if (clone[i] < min) {
        min = clone[i];
      }
    }
    int dValue = max - min;
    int[] countArray = new int[dValue + 1];
    for (int value : clone) {
      countArray[value - min]++;
    }
    // 統(tǒng)計(jì)數(shù)組做變形，后邊的元素等于前面的元素之和
    for (int i = 1; i < countArray.length; i++) {
      countArray[i] += countArray[i - 1];
    }
    // 倒序遍歷原始數(shù)組，從統(tǒng)計(jì)數(shù)組中找到正確的位置，輸出到結(jié)果數(shù)組
    int[] sortedArray = new int[clone.length];
    for (int i = clone.length - 1; i >= 0; i--) {
      // 給sortedArray的當(dāng)前位置賦值
      sortedArray[countArray[clone[i] - min] - 1] = clone[i];
      // 給countArray的位置的值--
      countArray[clone[i] - min]--;
    }
    return sortedArray;
  }

基數(shù)排序

  1. 取得數(shù)組中的最大數(shù)，并取得位數(shù)；
  2. arr為原始數(shù)組，從最低位開始取每個(gè)位組成radix數(shù)組；
  3. 對radix進(jìn)行計(jì)數(shù)排序
  /** 基數(shù)排序 */
  private static void radixSort(int[] clone) {
    int maxLength = 0;
    // 最大位數(shù)
    for (int i : clone) {
      int length = String.valueOf(i).length();
      maxLength = Math.max(length, maxLength);
    }
    List<List<Integer>> list =
        new ArrayList<List<Integer>>() {
          {
            // 0-9
            for (int i = 0; i < 10; i++) {
              add(new ArrayList<>());
            }
          }
        };
    for (int i = 0, temp = 1; i < maxLength; temp *= 10, i++) {
      for (int value : clone) {
        list.get((value / temp) % 10).add(value);
      }
      for (int j = 0, k = 0, l = list.size(); j < l; j++) {
        while (!list.get(j).isEmpty()) {
          clone[k] = list.get(j).get(0);
          list.get(j).remove(0);
          k++;
        }
      }
    }
  }

桶排序

  1. 設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶子。
  2. 尋訪序列，并且把項(xiàng)目一個(gè)一個(gè)放到對應(yīng)的桶子去。
  3. 對每個(gè)不是空的桶子進(jìn)行排序。
  4. 從不是空的桶子里把項(xiàng)目再放回原來的序列中。
 /** 桶排序 */
  private static int[] bucketSort(int[] clone) {
    int maxLength = 0, minLength = 0;
    // 最大位數(shù)and最小位數(shù)
    for (int i = 0, j = clone.length; i < j; i++) {
      int length = String.valueOf(clone[i]).length();
      maxLength = Math.max(length, maxLength);
      if (i == 0) {
        minLength = length;
      } else {
        minLength = Math.min(length, minLength);
      }
    }
    // 新建一個(gè)桶的集合
    List<LinkedList<Integer>> buckets = new ArrayList<>();
    for (int i = 0, j = maxLength - minLength + 1; i < j; i++) {
      // 新建一個(gè)桶，并將其添加到桶的集合中去。
      buckets.add(new LinkedList<>());
    }
    for (int i : clone) {
      int index = String.valueOf(i).length() - 1;
      LinkedList<Integer> integers = buckets.get(index);
      integers.add(i);
    }
    int[] finalArr = new int[clone.length];
    int tempIndex = 0;
    // 計(jì)數(shù)排序
    for (LinkedList<Integer> integers : buckets) {
      if (integers.size() > 0) {
        int max = integers.get(0);
        int min = integers.get(0);
        for (Integer i : integers) {
          if (i > max) {
            max = i;
          }
          if (i < min) {
            min = i;
          }
        }
        int dValue = max - min;
        int[] countArray = new int[dValue + 1];
        for (int value : integers) {
          countArray[value - min]++;
        }
        // 統(tǒng)計(jì)數(shù)組做變形，后邊的元素等于前面的元素之和
        for (int i = 1; i < countArray.length; i++) {
          countArray[i] += countArray[i - 1];
        }
        // 倒序遍歷原始數(shù)組，從統(tǒng)計(jì)數(shù)組中找到正確的位置，輸出到結(jié)果數(shù)組
        Integer[] sortedArray = new Integer[integers.size()];
        for (int i = integers.size() - 1; i >= 0; i--) {
          // 給sortedArray的當(dāng)前位置賦值
          sortedArray[countArray[integers.get(i) - min] - 1] = integers.get(i);
          // 給countArray的位置的值--
          countArray[integers.get(i) - min]--;
        }
        for (Integer integer : sortedArray) {
          finalArr[tempIndex++] = integer;
        }
      }
    }
    return finalArr;
  }

歸并排序

  1. 把長度為n的輸入序列分成兩個(gè)長度為n/2的子序列；
  2. 對這兩個(gè)子序列分別采用歸并排序；
  3. 將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。
  /**
   * 歸并排序
   *
   * @param ints 數(shù)組
   * @param start 左角標(biāo)
   * @param end 右角標(biāo)
   * @param tempArr 輔助數(shù)組
   */
  private static void mergeSort(int[] ints, int start, int end, int[] tempArr) {
    // 當(dāng)子序列中只有一個(gè)元素時(shí)結(jié)束遞歸
    if (start < end) {
      // 劃分子序列
      int mid = (start + end) / 2;
      // 對左側(cè)子序列進(jìn)行遞歸排序
      mergeSort(ints, start, mid, tempArr);
      // 對右側(cè)子序列進(jìn)行遞歸排序
      mergeSort(ints, mid + 1, end, tempArr);
      // 合并
      merge(ints, start, mid, end, tempArr);
    }
  }
  /** 兩路歸并算法，兩個(gè)排好序的子序列合并為一個(gè)子序列 */
  private static void merge(int[] ints, int left, int mid, int right, int[] tempArr) {
    int p1 = left, p2 = mid + 1, k = left;
    while (p1 <= mid && p2 <= right) {
      if (ints[p1] <= ints[p2]) {
        tempArr[k++] = ints[p1++];
      } else {
        tempArr[k++] = ints[p2++];
      }
    }
    while (p1 <= mid) {
      // 如果第一個(gè)序列未檢測完，直接將后面所有元素加到合并的序列中
      tempArr[k++] = ints[p1++];
    }
    while (p2 <= right) {
      tempArr[k++] = ints[p2++];
    }
    // 復(fù)制回原素組
    if (right + 1 - left >= 0) {
      System.arraycopy(tempArr, left, ints, left, right + 1 - left);
    }
  }

希爾排序

  1. 選擇一個(gè)增量序列t1，t2，…，tk，其中ti>tj，tk=1；
  2. 按增量序列個(gè)數(shù)k，對序列進(jìn)行k 趟排序；
  3. 每趟排序，根據(jù)對應(yīng)的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進(jìn)行直接插入排序。僅增量因子為1 時(shí)，整個(gè)序列作為一個(gè)表來處理，表長度即為整個(gè)序列的長度。
  /** 希爾排序 */
  public static void shellSort(int[] clone) {
    // 步長逐漸減小
    for (int gap = clone.length / 2; gap > 0; gap /= 2) {
      // 在同一步長內(nèi)
      for (int i = gap; i < clone.length; i++) {
        // 同一步長內(nèi)排序方式是插入排序
        int temp = clone[i], j;
        // j-gap代表有序數(shù)組中最大數(shù)的下標(biāo)，j-pag表示有序數(shù)組的前一個(gè)元素，減pag是減去偏移量就是步長
        for (j = i; j >= gap && temp < clone[j - gap]; j -= gap) {
          // 原有序數(shù)組最大的后移一位
          clone[j] = clone[j - gap];
        }
        // 找到了合適的位置插入
        clone[j] = temp;
      }
    }
  }

堆排序

  1. 將初始待排序關(guān)鍵字序列(R1,R2….Rn)構(gòu)建成大頂堆，此堆為初始的無序區(qū)；
  2. 將堆頂元素R[1]與最后一個(gè)元素R[n]交換，此時(shí)得到新的無序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2…n-1]<=R[n]；
  3. 由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要對當(dāng)前無序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆，然后再次將R[1]與無序區(qū)最后一個(gè)元素交換，得到新的無序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復(fù)此過程直到有序區(qū)的元素個(gè)數(shù)為n-1，則整個(gè)排序過程完成。
 /** 堆排序 */
  private static void heapSort(int[] clone) {
    // 創(chuàng)建堆
    for (int i = (clone.length - 1) / 2; i >= 0; i--) {
      // 從第一個(gè)非葉子結(jié)點(diǎn)從下至上，從右至左調(diào)整結(jié)構(gòu)
      adjustHeap(clone, i, clone.length);
    }

    // 調(diào)整堆結(jié)構(gòu),交換堆頂元素與末尾元素
    for (int i = clone.length - 1; i > 0; i--) {
      // 將堆頂元素與末尾元素進(jìn)行交換
      clone[i] = clone[i]+clone[0];
      clone[0] = clone[i]-clone[0];
      clone[i] = clone[i]-clone[0];
      // 重新對堆進(jìn)行調(diào)整
      adjustHeap(clone, 0, i);
    }
  }

  /**
   * 調(diào)整堆
   *
   * @param arr 待排序列
   * @param parent 父節(jié)點(diǎn)
   * @param length 待排序列尾元素索引
   */
  private static void adjustHeap(int[] arr, int parent, int length) {
    // 將temp作為父節(jié)點(diǎn)
    int temp = arr[parent];
    // 左孩子
    int lChild = 2 * parent + 1;

    while (lChild < length) {
      // 右孩子
      int rChild = lChild + 1;
      // 如果有右孩子結(jié)點(diǎn)，并且右孩子結(jié)點(diǎn)的值大于左孩子結(jié)點(diǎn)，則選取右孩子結(jié)點(diǎn)
      if (rChild < length && arr[lChild] < arr[rChild]) {
        lChild++;
      }
      // 如果父結(jié)點(diǎn)的值已經(jīng)大于孩子結(jié)點(diǎn)的值，則直接結(jié)束
      if (temp >= arr[lChild]) {
        break;
      }
      // 把孩子結(jié)點(diǎn)的值賦給父結(jié)點(diǎn)
      arr[parent] = arr[lChild];
      // 選取孩子結(jié)點(diǎn)的左孩子結(jié)點(diǎn),繼續(xù)向下篩選
      parent = lChild;
      lChild = 2 * lChild + 1;
    }
    arr[parent] = temp;
  }

練習(xí)代碼

import java.util.*;

/**
 * @author: shihchieh.ma
 * @create: 2020/6/15 6:13 下午
 * @email: shihchieh.ma@gail.com
 * @description:
 */
public class Sort {

  public static final int[] INTS = {
    24, 352, 23, 4, 1, 421, 5, 6, 436, 7, 86, 97, 9, 74, 34, 234, 1, 3, 6, 7
    //    10, 8, 6, 4, 2
  };

  /**
   * @param n 生成n個(gè)元素的隨機(jī)數(shù)組
   * @param rangeL 隨機(jī)范圍[rangeL
   * @param rangeR rangeR]
   * @return 返回一個(gè)隨機(jī) int 型數(shù)組
   */
  public static int[] gennerateArray(int n, int rangeL, int rangeR) {
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = (int) (Math.random() * (rangeR - rangeL + 1)) + rangeL;
    }
    return arr;
  }

  public static void main(String[] args) {
    //        int[] INTS = gennerateArray(10000, 1,10001);
    long startTime, endTime;
    //    冒泡排序
    int[] bubbleArr = INTS.clone();
    startTime = System.currentTimeMillis();
    bubbleSort(bubbleArr);
    endTime = System.currentTimeMillis();
    printArray("冒泡排序:", bubbleArr, endTime - startTime);

    //    選擇排序
    int[] selectionArr = INTS.clone();
    startTime = System.currentTimeMillis();
    selectionSort(selectionArr);
    endTime = System.currentTimeMillis();
    printArray("選擇排序:", selectionArr, endTime - startTime);

    //    插入排序
    int[] insertArr = INTS.clone();
    startTime = System.currentTimeMillis();
    insertSort(insertArr);
    endTime = System.currentTimeMillis();
    printArray("插入排序:", insertArr, endTime - startTime);

    //    快速排序
    int[] quickArr = INTS.clone();
    startTime = System.currentTimeMillis();
    quickSort(quickArr, 0, quickArr.length - 1);
    endTime = System.currentTimeMillis();
    printArray("快速排序:", quickArr, endTime - startTime);

    //    計(jì)數(shù)排序
    int[] countArr = INTS.clone();
    startTime = System.currentTimeMillis();
    int[] countSort = countSort(countArr);
    endTime = System.currentTimeMillis();
    printArray("計(jì)數(shù)排序:", countSort, endTime - startTime);

    //    基數(shù)排序
    int[] radixArr = INTS.clone();
    startTime = System.currentTimeMillis();
    radixSort(radixArr);
    endTime = System.currentTimeMillis();
    printArray("基數(shù)排序:", radixArr, endTime - startTime);

    // 桶排序
    int[] bucketArr = INTS.clone();
    startTime = System.currentTimeMillis();
    int[] bucketSort = bucketSort(bucketArr);
    endTime = System.currentTimeMillis();
    printArray("桶排序:", bucketSort, endTime - startTime);

    // 歸并排序
    int[] mergeArr = INTS.clone();
    startTime = System.currentTimeMillis();
    mergeSort(mergeArr, 0, mergeArr.length - 1, new int[mergeArr.length]);
    endTime = System.currentTimeMillis();
    printArray("歸并排序:", mergeArr, endTime - startTime);

    // 希爾排序
    int[] shellArr = INTS.clone();
    startTime = System.currentTimeMillis();
    mergeSort(shellArr, 0, shellArr.length - 1, new int[shellArr.length]);
    endTime = System.currentTimeMillis();
    printArray("希爾排序:", shellArr, endTime - startTime);

    // 堆排序
    int[] heapArr = INTS.clone();
    startTime = System.currentTimeMillis();
    heapSort(heapArr);
    endTime = System.currentTimeMillis();
    printArray("堆排序:", heapArr, endTime - startTime);
  }

  /** 冒泡排序 */
  private static void bubbleSort(int[] clone) {
    for (int i = 0, j = clone.length; i < j; i++) {
      for (int k = 0, l = j - 1 - i; k < l; k++) {
        if (clone[k] > clone[k + 1]) {
          clone[k] = clone[k] ^ clone[k + 1];
          clone[k + 1] = clone[k] ^ clone[k + 1];
          clone[k] = clone[k] ^ clone[k + 1];
        }
      }
    }
  }

  /** 選擇排序 */
  private static void selectionSort(int[] clone) {
    for (int i = 0, j = clone.length; i < j; i++) {
      int minIndex = i;
      for (int k = i; k < j; k++) {
        if (clone[k] < clone[minIndex]) {
          minIndex = k;
        }
      }
      if (minIndex != i) {
        clone[i] = clone[i] + clone[minIndex];
        clone[minIndex] = clone[i] - clone[minIndex];
        clone[i] = clone[i] - clone[minIndex];
      }
    }
  }

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

  /**
   * 快速排序
   *
   * @param clone 數(shù)組
   * @param leftIndex 左邊角標(biāo) 初始0
   * @param rightIndex 右邊角標(biāo) 初始length-1
   */
  private static void quickSort(int[] clone, int leftIndex, int rightIndex) {
    // temp-基準(zhǔn)位
    int i, j, temp;
    if (leftIndex > rightIndex) {
      return;
    }
    i = leftIndex;
    j = rightIndex;
    temp = clone[leftIndex];
    while (i < j) {
      // 先右邊，往左遞減,找一個(gè)小于基準(zhǔn)位的數(shù)
      // 當(dāng)右邊的角標(biāo)位置所在的數(shù)>基準(zhǔn)位的數(shù)時(shí)，繼續(xù)從右往左找（同時(shí) j 索引-1)
      // 找到就跳出 while循環(huán)
      while (temp <= clone[j] && i < j) {
        j--;
      }
      // 再左邊，往右遞增
      // 如上
      while (temp >= clone[i] && i < j) {
        i++;
      }
      // 滿足條件則交換
      if (i < j) {
        clone[i] = clone[i] + clone[j];
        clone[j] = clone[i] - clone[j];
        clone[i] = clone[i] - clone[j];
      }
    }
    // i=j 左右在同一位置
    // 最后將基準(zhǔn)為與i和j相等位置的數(shù)字交換
    clone[leftIndex] = clone[i];
    clone[i] = temp;
    // 左半數(shù)組<(i或j所在索引的數(shù))<右半數(shù)組
    // 也就是說(i或j所在索引的數(shù))已經(jīng)確定排序位置，就不用再排序了，
    // 相同的方法分別處理左右數(shù)組
    // 遞歸調(diào)用左半數(shù)組
    quickSort(clone, leftIndex, j - 1);
    // 遞歸調(diào)用右半數(shù)組
    quickSort(clone, j + 1, rightIndex);
  }

  /** 計(jì)數(shù)排序 */
  private static int[] countSort(int[] clone) {
    int max = clone[0];
    int min = clone[0];
    for (int i = 1, j = clone.length; i < j; i++) {
      if (clone[i] > max) {
        max = clone[i];
      }
      if (clone[i] < min) {
        min = clone[i];
      }
    }
    int dValue = max - min;
    int[] countArray = new int[dValue + 1];
    for (int value : clone) {
      countArray[value - min]++;
    }
    // 統(tǒng)計(jì)數(shù)組做變形，后邊的元素等于前面的元素之和
    for (int i = 1; i < countArray.length; i++) {
      countArray[i] += countArray[i - 1];
    }
    // 倒序遍歷原始數(shù)組，從統(tǒng)計(jì)數(shù)組中找到正確的位置，輸出到結(jié)果數(shù)組
    int[] sortedArray = new int[clone.length];
    for (int i = clone.length - 1; i >= 0; i--) {
      // 給sortedArray的當(dāng)前位置賦值
      sortedArray[countArray[clone[i] - min] - 1] = clone[i];
      // 給countArray的位置的值--
      countArray[clone[i] - min]--;
    }
    return sortedArray;
  }

  /** 基數(shù)排序 */
  private static void radixSort(int[] clone) {
    int maxLength = 0;
    // 最大位數(shù)
    for (int i : clone) {
      int length = String.valueOf(i).length();
      maxLength = Math.max(length, maxLength);
    }
    List<List<Integer>> list =
        new ArrayList<List<Integer>>() {
          {
            // 0-9
            for (int i = 0; i < 10; i++) {
              add(new ArrayList<>());
            }
          }
        };
    for (int i = 0, temp = 1; i < maxLength; temp *= 10, i++) {
      for (int value : clone) {
        list.get((value / temp) % 10).add(value);
      }
      for (int j = 0, k = 0, l = list.size(); j < l; j++) {
        while (!list.get(j).isEmpty()) {
          clone[k] = list.get(j).get(0);
          list.get(j).remove(0);
          k++;
        }
      }
    }
  }

  /** 桶排序 */
  private static int[] bucketSort(int[] clone) {
    int maxLength = 0, minLength = 0;
    // 最大位數(shù)and最小位數(shù)
    for (int i = 0, j = clone.length; i < j; i++) {
      int length = String.valueOf(clone[i]).length();
      maxLength = Math.max(length, maxLength);
      if (i == 0) {
        minLength = length;
      } else {
        minLength = Math.min(length, minLength);
      }
    }
    // 新建一個(gè)桶的集合
    List<LinkedList<Integer>> buckets = new ArrayList<>();
    for (int i = 0, j = maxLength - minLength + 1; i < j; i++) {
      // 新建一個(gè)桶，并將其添加到桶的集合中去。
      buckets.add(new LinkedList<>());
    }
    for (int i : clone) {
      int index = String.valueOf(i).length() - 1;
      LinkedList<Integer> integers = buckets.get(index);
      integers.add(i);
    }
    int[] finalArr = new int[clone.length];
    int tempIndex = 0;
    // 計(jì)數(shù)排序
    for (LinkedList<Integer> integers : buckets) {
      if (integers.size() > 0) {
        int max = integers.get(0);
        int min = integers.get(0);
        for (Integer i : integers) {
          if (i > max) {
            max = i;
          }
          if (i < min) {
            min = i;
          }
        }
        int dValue = max - min;
        int[] countArray = new int[dValue + 1];
        for (int value : integers) {
          countArray[value - min]++;
        }
        // 統(tǒng)計(jì)數(shù)組做變形，后邊的元素等于前面的元素之和
        for (int i = 1; i < countArray.length; i++) {
          countArray[i] += countArray[i - 1];
        }
        // 倒序遍歷原始數(shù)組，從統(tǒng)計(jì)數(shù)組中找到正確的位置，輸出到結(jié)果數(shù)組
        Integer[] sortedArray = new Integer[integers.size()];
        for (int i = integers.size() - 1; i >= 0; i--) {
          // 給sortedArray的當(dāng)前位置賦值
          sortedArray[countArray[integers.get(i) - min] - 1] = integers.get(i);
          // 給countArray的位置的值--
          countArray[integers.get(i) - min]--;
        }
        for (Integer integer : sortedArray) {
          finalArr[tempIndex++] = integer;
        }
      }
    }
    return finalArr;
  }

  /**
   * 歸并排序
   *
   * @param ints 數(shù)組
   * @param start 左角標(biāo)
   * @param end 右角標(biāo)
   * @param tempArr 輔助數(shù)組
   */
  private static void mergeSort(int[] ints, int start, int end, int[] tempArr) {
    // 當(dāng)子序列中只有一個(gè)元素時(shí)結(jié)束遞歸
    if (start < end) {
      // 劃分子序列
      int mid = (start + end) / 2;
      // 對左側(cè)子序列進(jìn)行遞歸排序
      mergeSort(ints, start, mid, tempArr);
      // 對右側(cè)子序列進(jìn)行遞歸排序
      mergeSort(ints, mid + 1, end, tempArr);
      // 合并
      merge(ints, start, mid, end, tempArr);
    }
  }
  /** 兩路歸并算法，兩個(gè)排好序的子序列合并為一個(gè)子序列 */
  private static void merge(int[] ints, int left, int mid, int right, int[] tempArr) {
    int p1 = left, p2 = mid + 1, k = left;
    while (p1 <= mid && p2 <= right) {
      if (ints[p1] <= ints[p2]) {
        tempArr[k++] = ints[p1++];
      } else {
        tempArr[k++] = ints[p2++];
      }
    }
    while (p1 <= mid) {
      // 如果第一個(gè)序列未檢測完，直接將后面所有元素加到合并的序列中
      tempArr[k++] = ints[p1++];
    }
    while (p2 <= right) {
      tempArr[k++] = ints[p2++];
    }
    // 復(fù)制回原素組
    if (right + 1 - left >= 0) {
      System.arraycopy(tempArr, left, ints, left, right + 1 - left);
    }
  }

  /** 希爾排序 */
  private static void shellSort(int[] clone) {
    // 步長逐漸減小
    for (int gap = clone.length / 2; gap > 0; gap /= 2) {
      // 在同一步長內(nèi)
      for (int i = gap; i < clone.length; i++) {
        // 同一步長內(nèi)排序方式是插入排序
        int temp = clone[i], j;
        // j-gap代表有序數(shù)組中最大數(shù)的下標(biāo)，j-pag表示有序數(shù)組的前一個(gè)元素，減pag是減去偏移量就是步長
        for (j = i; j >= gap && temp < clone[j - gap]; j -= gap) {
          // 原有序數(shù)組最大的后移一位
          clone[j] = clone[j - gap];
        }
        // 找到了合適的位置插入
        clone[j] = temp;
      }
    }
  }

  /** 堆排序 */
  private static void heapSort(int[] clone) {
    // 創(chuàng)建堆
    for (int i = (clone.length - 1) / 2; i >= 0; i--) {
      // 從第一個(gè)非葉子結(jié)點(diǎn)從下至上，從右至左調(diào)整結(jié)構(gòu)
      adjustHeap(clone, i, clone.length);
    }

    // 調(diào)整堆結(jié)構(gòu),交換堆頂元素與末尾元素
    for (int i = clone.length - 1; i > 0; i--) {
      // 將堆頂元素與末尾元素進(jìn)行交換
      clone[i] = clone[i]+clone[0];
      clone[0] = clone[i]-clone[0];
      clone[i] = clone[i]-clone[0];
      // 重新對堆進(jìn)行調(diào)整
      adjustHeap(clone, 0, i);
    }
  }

  /**
   * 調(diào)整堆
   *
   * @param arr 待排序列
   * @param parent 父節(jié)點(diǎn)
   * @param length 待排序列尾元素索引
   */
  private static void adjustHeap(int[] arr, int parent, int length) {
    // 將temp作為父節(jié)點(diǎn)
    int temp = arr[parent];
    // 左孩子
    int lChild = 2 * parent + 1;

    while (lChild < length) {
      // 右孩子
      int rChild = lChild + 1;
      // 如果有右孩子結(jié)點(diǎn)，并且右孩子結(jié)點(diǎn)的值大于左孩子結(jié)點(diǎn)，則選取右孩子結(jié)點(diǎn)
      if (rChild < length && arr[lChild] < arr[rChild]) {
        lChild++;
      }
      // 如果父結(jié)點(diǎn)的值已經(jīng)大于孩子結(jié)點(diǎn)的值，則直接結(jié)束
      if (temp >= arr[lChild]) {
        break;
      }
      // 把孩子結(jié)點(diǎn)的值賦給父結(jié)點(diǎn)
      arr[parent] = arr[lChild];
      // 選取孩子結(jié)點(diǎn)的左孩子結(jié)點(diǎn),繼續(xù)向下篩選
      parent = lChild;
      lChild = 2 * lChild + 1;
    }
    arr[parent] = temp;
  }

  private static void printArray(String name, int[] ints, long time) {
    for (int anInt : ints) {
      System.out.print("_" + anInt + "_");
    }
    System.out.println("\t");
    System.out.println(name + "耗時(shí):" + time);
    System.out.println();
  }
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容