八大排序算法

image.png

工具类

生成随机整数数组

  1. public class RandomNum {
  3.     /**
  4.      * @param len    数组的长度
  5.      * @param maxNum 最大值
  6.      * @param minNum 最小值
  7.      * @return 生成随机整数数组
  8.      */
  9.     public static int[] getRandomInts(int len,  int minNum, int maxNum) {
  10.         int[] ints = new int[len];
  11.         for (int i = 0; i < len; i++) {
  12.             ints[i] = (int) (Math.random() * (maxNum - minNum + 1) + minNum);
  13.         }
  14.         return ints;
  15.     }
  16. }

验证排序

  1. public class Verify {
  3.     public static void show(int[] nums) {
  4.         int len = nums.length;
  5.         if (len == 0) {
  6.             System.out.println("nums is null");
  7.             return;
  8.         }
  9.         for (int num : nums) {
  10.             System.out.print(num + " ");
  11.         }
  12.         System.out.println();
  13.     }
  15.     /**
  16.      * 验证是否排好序
  17.      *
  18.      * @param nums 待验证数组
  19.      * @param flag 升序标志 true: 升序 false: 降序
  20.      * @return 是否排好序
  21.      */
  22.     public static boolean isSorted(int[] nums, boolean flag) {
  23.         int len = nums.length;
  24.         if (len <= 1) {
  25.             return true;
  26.         }
  27.         //升序
  28.         if (flag) {
  29.             for (int i = 0, j = 1; j < len; i++, j++) {
  30.                 if (nums[i] > nums[j]) {
  31.                     return false;
  32.                 }
  33.             }
  34.             return true;
  35.         } else {
  36.             for (int i = 0, j = 1; j < len; i++, j++) {
  37.                 if (nums[i] < nums[j]) {
  38.                     return false;
  39.                 }
  40.             }
  41.             return true;
  42.         }
  43.     }
  44. }

直接插入排序

基本思想

常人们整理桥牌的方法是一张一张的来，将每一张牌插入到其他已经有序的牌中的适当位置。在计算机的实现中，为了要给插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。

算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

算法 - 图2

代码实现

  1. void sort(int[] nums) {
  2.     int len = nums.length;
  3.     if (len <= 1) return;
  4.     for (int i = 1; i < len; i++) {
  5.         int j;
  6.         int curr = nums[i];
  7.         // 以当前元素为基准，向前遍历，和大于curr的元素交换位置
  8.         for (j = i; j > 0 && curr < nums[j - 1]; j--) {
  9.             nums[j] = nums[j - 1];
  10.         }
  11.         nums[j] = curr;
  12.     }
  13. }

复杂度分析

直接插入排序复杂度如下：

平均时间复杂度 最好情况 最坏情况 空间复杂度
O(n²) O(n²) O(n²) O(1)

比较与总结

插入排序所需的时间取决于输入元素的初始顺序。例如，对一个很大且其中的元素已经有序(或接近有序)的数组进行排序将会比随机顺序的数组或是逆序数组进行排序要快得多

希尔排序

冒泡排序

基本思想

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法描述

冒泡排序算法的运作如下：

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

算法 - 图3

代码实现

快速排序

基本思想