美文网首页
排序笔记

排序笔记

作者: ShihChieh_Ma | 来源:发表于2020-06-28 11:16 被阅读0次
    /**
 * @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个元素的随机数组
   * @param rangeL 随机范围[rangeL
   * @param rangeR rangeR]
   * @return 返回一个随机 int 型数组
   */
  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);

    //    计数排序
    int[] countArr = INTS.clone();
    startTime = System.currentTimeMillis();
    int[] countSort = countSort(countArr);
    endTime = System.currentTimeMillis();
    printArray("计数排序:", countSort, endTime - startTime);

    //    基数排序
    int[] radixArr = INTS.clone();
    startTime = System.currentTimeMillis();
    radixSort(radixArr);
    endTime = System.currentTimeMillis();
    printArray("基数排序:", 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 + "耗时:" + time);
    System.out.println();
  }
}

    冒泡排序

    1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
    2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
    3. 针对所有的元素重复以上的步骤，除了最后一个。
    4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
      /** 冒泡排序 */
  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. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
    2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
    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. 第一个元素开始，该元素可以认为已经被排序
    2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
    3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
    4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
    5. 将新元素插入到该位置后
    6. 重复步骤 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. 选取第一个数为基准
    2. 将比基准小的数交换到前面，比基准大的数交换到后面
    3. 对左右区间重复第二步，直到各区间只有一个数
      /**
   * 快速排序
   *
   * @param clone 数组
   * @param leftIndex 左边角标 初始0
   * @param rightIndex 右边角标 初始length-1
   */
  private static void quickSort(int[] clone, int leftIndex, int rightIndex) {
    // temp-基准位
    int i, j, temp;
    if (leftIndex > rightIndex) {
      return;
    }
    i = leftIndex;
    j = rightIndex;
    temp = clone[leftIndex];
    while (i < j) {
      // 先右边，往左递减,找一个小于基准位的数
      // 当右边的角标位置所在的数>基准位的数时，继续从右往左找（同时 j 索引-1)
      // 找到就跳出 while循环
      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 左右在同一位置
    // 最后将基准为与i和j相等位置的数字交换
    clone[leftIndex] = clone[i];
    clone[i] = temp;
    // 左半数组<(i或j所在索引的数)<右半数组
    // 也就是说(i或j所在索引的数)已经确定排序位置，就不用再排序了，
    // 相同的方法分别处理左右数组
    // 递归调用左半数组
    quickSort(clone, leftIndex, j - 1);
    // 递归调用右半数组
    quickSort(clone, j + 1, rightIndex);
  }

    计数排序

    1. 找出待排序的数组中最大和最小的元素；
    2. 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
    3. 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；
    4. 向填充目标数组：将每个元素 i 放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去 1；

    当数组最大和最小差值过大时，不适合计数排序
    当数组元素不是整数时，不适合用计数排序

      /** 计数排序 */
  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]++;
    }
    // 统计数组做变形，后边的元素等于前面的元素之和
    for (int i = 1; i < countArray.length; i++) {
      countArray[i] += countArray[i - 1];
    }
    // 倒序遍历原始数组，从统计数组中找到正确的位置，输出到结果数组
    int[] sortedArray = new int[clone.length];
    for (int i = clone.length - 1; i >= 0; i--) {
      // 给sortedArray的当前位置赋值
      sortedArray[countArray[clone[i] - min] - 1] = clone[i];
      // 给countArray的位置的值--
      countArray[clone[i] - min]--;
    }
    return sortedArray;
  }

    基数排序

    1. 取得数组中的最大数，并取得位数；
    2. arr为原始数组，从最低位开始取每个位组成radix数组；
    3. 对radix进行计数排序
      /** 基数排序 */
  private static void radixSort(int[] clone) {
    int maxLength = 0;
    // 最大位数
    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. 设置一个定量的数组当作空桶子。
    2. 寻访序列，并且把项目一个一个放到对应的桶子去。
    3. 对每个不是空的桶子进行排序。
    4. 从不是空的桶子里把项目再放回原来的序列中。
     /** 桶排序 */
  private static int[] bucketSort(int[] clone) {
    int maxLength = 0, minLength = 0;
    // 最大位数and最小位数
    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);
      }
    }
    // 新建一个桶的集合
    List<LinkedList<Integer>> buckets = new ArrayList<>();
    for (int i = 0, j = maxLength - minLength + 1; i < j; i++) {
      // 新建一个桶，并将其添加到桶的集合中去。
      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;
    // 计数排序
    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]++;
        }
        // 统计数组做变形，后边的元素等于前面的元素之和
        for (int i = 1; i < countArray.length; i++) {
          countArray[i] += countArray[i - 1];
        }
        // 倒序遍历原始数组，从统计数组中找到正确的位置，输出到结果数组
        Integer[] sortedArray = new Integer[integers.size()];
        for (int i = integers.size() - 1; i >= 0; i--) {
          // 给sortedArray的当前位置赋值
          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的输入序列分成两个长度为n/2的子序列；
    2. 对这两个子序列分别采用归并排序；
    3. 将两个排序好的子序列合并成一个最终的排序序列。
      /**
   * 归并排序
   *
   * @param ints 数组
   * @param start 左角标
   * @param end 右角标
   * @param tempArr 辅助数组
   */
  private static void mergeSort(int[] ints, int start, int end, int[] tempArr) {
    // 当子序列中只有一个元素时结束递归
    if (start < end) {
      // 划分子序列
      int mid = (start + end) / 2;
      // 对左侧子序列进行递归排序
      mergeSort(ints, start, mid, tempArr);
      // 对右侧子序列进行递归排序
      mergeSort(ints, mid + 1, end, tempArr);
      // 合并
      merge(ints, start, mid, end, tempArr);
    }
  }
  /** 两路归并算法，两个排好序的子序列合并为一个子序列 */
  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) {
      // 如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
      tempArr[k++] = ints[p1++];
    }
    while (p2 <= right) {
      tempArr[k++] = ints[p2++];
    }
    // 复制回原素组
    if (right + 1 - left >= 0) {
      System.arraycopy(tempArr, left, ints, left, right + 1 - left);
    }
  }

    希尔排序

    1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
    2. 按增量序列个数k，对序列进行k 趟排序；
    3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
      /** 希尔排序 */
  public static void shellSort(int[] clone) {
    // 步长逐渐减小
    for (int gap = clone.length / 2; gap > 0; gap /= 2) {
      // 在同一步长内
      for (int i = gap; i < clone.length; i++) {
        // 同一步长内排序方式是插入排序
        int temp = clone[i], j;
        // j-gap代表有序数组中最大数的下标，j-pag表示有序数组的前一个元素，减pag是减去偏移量就是步长
        for (j = i; j >= gap && temp < clone[j - gap]; j -= gap) {
          // 原有序数组最大的后移一位
          clone[j] = clone[j - gap];
        }
        // 找到了合适的位置插入
        clone[j] = temp;
      }
    }
  }

    堆排序

    1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
    2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
    3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
     /** 堆排序 */
  private static void heapSort(int[] clone) {
    // 创建堆
    for (int i = (clone.length - 1) / 2; i >= 0; i--) {
      // 从第一个非叶子结点从下至上，从右至左调整结构
      adjustHeap(clone, i, clone.length);
    }

    // 调整堆结构,交换堆顶元素与末尾元素
    for (int i = clone.length - 1; i > 0; i--) {
      // 将堆顶元素与末尾元素进行交换
      clone[i] = clone[i]+clone[0];
      clone[0] = clone[i]-clone[0];
      clone[i] = clone[i]-clone[0];
      // 重新对堆进行调整
      adjustHeap(clone, 0, i);
    }
  }

  /**
   * 调整堆
   *
   * @param arr 待排序列
   * @param parent 父节点
   * @param length 待排序列尾元素索引
   */
  private static void adjustHeap(int[] arr, int parent, int length) {
    // 将temp作为父节点
    int temp = arr[parent];
    // 左孩子
    int lChild = 2 * parent + 1;

    while (lChild < length) {
      // 右孩子
      int rChild = lChild + 1;
      // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
      if (rChild < length && arr[lChild] < arr[rChild]) {
        lChild++;
      }
      // 如果父结点的值已经大于孩子结点的值，则直接结束
      if (temp >= arr[lChild]) {
        break;
      }
      // 把孩子结点的值赋给父结点
      arr[parent] = arr[lChild];
      // 选取孩子结点的左孩子结点,继续向下筛选
      parent = lChild;
      lChild = 2 * lChild + 1;
    }
    arr[parent] = temp;
  }

    练习代码

    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个元素的随机数组
   * @param rangeL 随机范围[rangeL
   * @param rangeR rangeR]
   * @return 返回一个随机 int 型数组
   */
  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);

    //    计数排序
    int[] countArr = INTS.clone();
    startTime = System.currentTimeMillis();
    int[] countSort = countSort(countArr);
    endTime = System.currentTimeMillis();
    printArray("计数排序:", countSort, endTime - startTime);

    //    基数排序
    int[] radixArr = INTS.clone();
    startTime = System.currentTimeMillis();
    radixSort(radixArr);
    endTime = System.currentTimeMillis();
    printArray("基数排序:", 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 数组
   * @param leftIndex 左边角标 初始0
   * @param rightIndex 右边角标 初始length-1
   */
  private static void quickSort(int[] clone, int leftIndex, int rightIndex) {
    // temp-基准位
    int i, j, temp;
    if (leftIndex > rightIndex) {
      return;
    }
    i = leftIndex;
    j = rightIndex;
    temp = clone[leftIndex];
    while (i < j) {
      // 先右边，往左递减,找一个小于基准位的数
      // 当右边的角标位置所在的数>基准位的数时，继续从右往左找（同时 j 索引-1)
      // 找到就跳出 while循环
      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 左右在同一位置
    // 最后将基准为与i和j相等位置的数字交换
    clone[leftIndex] = clone[i];
    clone[i] = temp;
    // 左半数组<(i或j所在索引的数)<右半数组
    // 也就是说(i或j所在索引的数)已经确定排序位置，就不用再排序了，
    // 相同的方法分别处理左右数组
    // 递归调用左半数组
    quickSort(clone, leftIndex, j - 1);
    // 递归调用右半数组
    quickSort(clone, j + 1, rightIndex);
  }

  /** 计数排序 */
  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]++;
    }
    // 统计数组做变形，后边的元素等于前面的元素之和
    for (int i = 1; i < countArray.length; i++) {
      countArray[i] += countArray[i - 1];
    }
    // 倒序遍历原始数组，从统计数组中找到正确的位置，输出到结果数组
    int[] sortedArray = new int[clone.length];
    for (int i = clone.length - 1; i >= 0; i--) {
      // 给sortedArray的当前位置赋值
      sortedArray[countArray[clone[i] - min] - 1] = clone[i];
      // 给countArray的位置的值--
      countArray[clone[i] - min]--;
    }
    return sortedArray;
  }

  /** 基数排序 */
  private static void radixSort(int[] clone) {
    int maxLength = 0;
    // 最大位数
    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;
    // 最大位数and最小位数
    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);
      }
    }
    // 新建一个桶的集合
    List<LinkedList<Integer>> buckets = new ArrayList<>();
    for (int i = 0, j = maxLength - minLength + 1; i < j; i++) {
      // 新建一个桶，并将其添加到桶的集合中去。
      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;
    // 计数排序
    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]++;
        }
        // 统计数组做变形，后边的元素等于前面的元素之和
        for (int i = 1; i < countArray.length; i++) {
          countArray[i] += countArray[i - 1];
        }
        // 倒序遍历原始数组，从统计数组中找到正确的位置，输出到结果数组
        Integer[] sortedArray = new Integer[integers.size()];
        for (int i = integers.size() - 1; i >= 0; i--) {
          // 给sortedArray的当前位置赋值
          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 数组
   * @param start 左角标
   * @param end 右角标
   * @param tempArr 辅助数组
   */
  private static void mergeSort(int[] ints, int start, int end, int[] tempArr) {
    // 当子序列中只有一个元素时结束递归
    if (start < end) {
      // 划分子序列
      int mid = (start + end) / 2;
      // 对左侧子序列进行递归排序
      mergeSort(ints, start, mid, tempArr);
      // 对右侧子序列进行递归排序
      mergeSort(ints, mid + 1, end, tempArr);
      // 合并
      merge(ints, start, mid, end, tempArr);
    }
  }
  /** 两路归并算法，两个排好序的子序列合并为一个子序列 */
  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) {
      // 如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
      tempArr[k++] = ints[p1++];
    }
    while (p2 <= right) {
      tempArr[k++] = ints[p2++];
    }
    // 复制回原素组
    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) {
      // 在同一步长内
      for (int i = gap; i < clone.length; i++) {
        // 同一步长内排序方式是插入排序
        int temp = clone[i], j;
        // j-gap代表有序数组中最大数的下标，j-pag表示有序数组的前一个元素，减pag是减去偏移量就是步长
        for (j = i; j >= gap && temp < clone[j - gap]; j -= gap) {
          // 原有序数组最大的后移一位
          clone[j] = clone[j - gap];
        }
        // 找到了合适的位置插入
        clone[j] = temp;
      }
    }
  }

  /** 堆排序 */
  private static void heapSort(int[] clone) {
    // 创建堆
    for (int i = (clone.length - 1) / 2; i >= 0; i--) {
      // 从第一个非叶子结点从下至上，从右至左调整结构
      adjustHeap(clone, i, clone.length);
    }

    // 调整堆结构,交换堆顶元素与末尾元素
    for (int i = clone.length - 1; i > 0; i--) {
      // 将堆顶元素与末尾元素进行交换
      clone[i] = clone[i]+clone[0];
      clone[0] = clone[i]-clone[0];
      clone[i] = clone[i]-clone[0];
      // 重新对堆进行调整
      adjustHeap(clone, 0, i);
    }
  }

  /**
   * 调整堆
   *
   * @param arr 待排序列
   * @param parent 父节点
   * @param length 待排序列尾元素索引
   */
  private static void adjustHeap(int[] arr, int parent, int length) {
    // 将temp作为父节点
    int temp = arr[parent];
    // 左孩子
    int lChild = 2 * parent + 1;

    while (lChild < length) {
      // 右孩子
      int rChild = lChild + 1;
      // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
      if (rChild < length && arr[lChild] < arr[rChild]) {
        lChild++;
      }
      // 如果父结点的值已经大于孩子结点的值，则直接结束
      if (temp >= arr[lChild]) {
        break;
      }
      // 把孩子结点的值赋给父结点
      arr[parent] = arr[lChild];
      // 选取孩子结点的左孩子结点,继续向下筛选
      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 + "耗时:" + time);
    System.out.println();
  }
}

    相关文章

      网友评论

          本文标题：排序笔记

          本文链接：https://www.haomeiwen.com/subject/sayhxktx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|排序笔记|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！