详解冒泡、插入、选择三种排序- 2021-0-12 21:25- 算法

冒泡排序

冒泡排序其实是说算法的执行过程像冒泡泡一样，将数据从左到右或是从右到左的浮动过去。冒泡算法是通过比较数组中两两相临的数值大小，如果是结果是逆向的则交换两值的位置，重复这个过程知道数组最终有序。

代码实现

  2. /**
  3.  * 冒泡算法
  4.  * 比较数组中相邻两个值的大小，并交换位置，将最小或最大的数分别放置在数组的首位或者末尾
  5.  *
  6.  * @author Bai
  7.  * @date 2021/8/22 10:49
  8.  */
  9. public class BubbleSort extends BaseSort {
  11.     /**
  12.      * 冒泡算法：升序排序
  13.      *
  14.      * @param arr
  15.      */
  16.     @Override
  17.     void ascSort (int[] arr) {
  18.         //边界
  19.         if (null == arr || arr.length < 2) {
  20.             return;
  21.         }
  22.         //倒循环：缩小每次循环的范围，去除已经排序完成的位置
  23.         for (int e = arr.length; e > 0; e--) {
  24.             //正循环: 主要是用于排序
  25.             for (int i = 0; i < e - 1; i++) {
  26.                 //相邻两个值进行比较 ，如果i位置的值大于i+1位置的值，则进行交换
  27.                 if (arr[i] > arr[i + 1]) {
  28.                     swap(arr, i, i + 1);
  29.                 }
  30.             }
  31.         }
  32.     }
  35.     /**
  36.      * 冒泡算法：正序排序
  37.      *
  38.      * @param arr
  39.      */
  40.     @Override
  41.     void descSort (int[] arr) {
  42.         //边界
  43.         if (null == arr || arr.length < 2) {
  44.             return;
  45.         }
  46.         //倒循环：缩小每次循环的范围，去除已经排序完成的位置
  47.         for (int e = arr.length; e > 0; e--) {
  48.             //正循环: 主要是用于排序
  49.             for (int i = 0; i < e - 1; i++) {
  50.                 //相邻两个值进行比较 ，如果i位置的值大于i+1位置的值，则进行交换
  51.                 if (arr[i] < arr[i + 1]) {
  52.                     swap(arr, i, i + 1);
  53.                 }
  54.             }
  55.         }
  56.     }
  57. }

时间复杂度O(n²)&空间复杂度O(1)

冒泡算法的平均时间复杂度是O(n²)，最坏时间复杂度也是O(n²)，而最好的时间复杂度是O(n)。冒泡算法需要循环两次来实现这个功能，第一次倒循环：缩小每次循环的范围，去除已经排序完成的位置；第二次正循环：实现相邻下标数据比较，并交换位置。循环一次的时间复杂度为O(n)，最坏情况下就是两次循环都要执行一遍，所以冒泡排序最坏的时间复杂度为O(n²)。

最好时间复杂度O(n)

最好时间复杂度O(n)的成立是建立在 数组本身已经是有序的基础上，只需要执行一遍最外层的循环，即可结束。使用一个变量记录内层循环的执行状态，是否进行了swap操作，如果循环一轮下来并未进行交换操作，那么就可以认为这个数组已经是有序的。

  1. /**
  2.      * 冒泡算法：算法最优写法
  3.      * 算法最好情况下时间复杂度是O(n),也就是数组本身已经是有序的状态下，只需要对数组进行一次循环，也就是O(n)
  4.      *
  5.      * @param arr
  6.      */
  7.     public static void bestSort (int[] arr) {
  8.         //边界
  9.         if (null == arr || arr.length < 2) {
  10.             return;
  11.         }
  12.         //倒循环：缩小每次循环的范围，去除已经排序完成的位置
  13.         for (int e = arr.length; e > 0; e--) {
  14.             //初始假设这个数组是有序
  15.             boolean orderly = true;
  16.             //正循环: 主要是用于排序
  17.             for (int i = 0; i < e - 1; i++) {
  18.                 //相邻两个值进行比较 ，如果i位置的值大于i+1位置的值，则进行交换
  19.                 if (arr[i] > arr[i + 1]) {
  20.                     swap(arr, i, i + 1);
  21.                     orderly = false;
  22.                 }
  23.             }
  24.             //循环一次后，如果数组数组是有序的，则无须再排序
  25.             if (orderly) {
  26.                 break;
  27.             }
  28.         }
  29.     }

测试

  2. /**
  3.  *    算法测试类
  4.  * @author Bai
  5.  * @date 2021/9/11 14:17
  6.  */
  7. public abstract class BaseSort {
  8.     private Integer forCnt = 100000;
  10.     public BaseSort () {
  11.     }
  13.     public BaseSort (Integer forCnt) {
  14.         this.forCnt = forCnt;
  15.     }
  17.     /**
  18.      * 升序排序
  19.      *
  20.      * @param arr
  21.      */
  22.     abstract void ascSort (int[] arr);
  24.     /**
  25.      * 降序排序
  26.      *
  27.      * @param arr
  28.      */
  29.     abstract void descSort (int[] arr);
  31.     public void ascForCheck () {
  32.         for (int i = 0; i < forCnt; i++) {
  33.             //升序
  34.             int[] arr = getArr();
  35.             int[] arr1 = arr.clone();
  36.             ascSort(arr);
  37.             ascCheck(arr, arr1);
  38.         }
  39.     }
  41.     public void descForCheck () {
  42.         for (int i = 0; i < forCnt; i++) {
  43.             //升序
  44.             int[] arr = getArr();
  45.             int[] arr1 = arr.clone();
  46.             descSort(arr);
  47.             descCheck(arr, arr1);
  48.         }
  49.     }
  51.     public static void run (BaseSort baseSort) {
  52.         baseSort.ascForCheck();
  53.         baseSort.descForCheck();
  54.     }
  56.     /**
  57.      * 该方法只使用 两个变量不是同一内存，否则会出现问题
  58.      *
  59.      * @param arr
  60.      * @param i
  61.      * @param j
  62.      */
  63.     public static void swap (int[] arr, int i, int j) {
  64.         int tmp = arr[i];
  65.         arr[i] = arr[j];
  66.         arr[j] = tmp;
  67.     }
  69.     public static int[] getArr () {
  70.         Random random = new Random();
  71.         int[] arr = new int[random.nextInt(1000)];
  72.         for (int i = 0; i < arr.length; i++) {
  73.             arr[i] = random.nextInt(10000);
  74.         }
  75.         return arr;
  76.     }
  78.     public static void ascCheck (int[] arr, int[] arr1) {
  79.         Arrays.sort(arr1);
  80.         check(arr, arr1);
  81.     }
  83.     public static void descCheck (int[] arr, int[] arr1) {
  84.         Integer[] trans = trans(arr1);
  85.         Arrays.sort(trans, Collections.reverseOrder());
  86.         check(arr, trans(trans));
  87.     }
  89.     public static void check (int[] arr, int[] arr1) {
  90.         for (int i = 0; i < arr.length; i++) {
  91.             if (arr[i] != arr1[i]) {
  92.                 System.out.println("↓----排序失败----↓");
  93.                 System.out.println(JSONObject.toJSONString(arr));
  94.                 System.out.println(JSONObject.toJSONString(arr1));
  95.                 System.out.println("↑----排序失败----↑");
  96.                 break;
  97.             }
  98.         }
  99.     }
  101.     public static Integer[] trans (int[] arr1) {
  102.         Integer[] integers = new Integer[arr1.length];
  103.         for (int i = 0; i < arr1.length; i++) {
  104.             integers[i] = arr1[i];
  105.         }
  106.         return integers;
  107.     }
  109.     public static int[] trans (Integer[] arr1) {
  110.         int[] integers = new int[arr1.length];
  111.         for (int i = 0; i < arr1.length; i++) {
  112.             integers[i] = arr1[i];
  113.         }
  114.         return integers;
  115.     }
  117.     public static void print (Object o) {
  118.         System.out.println(JSONObject.toJSONString(o));
  119.     }
  120. }
  1. public static void main (String[] args) {
  2.         run(new BubbleSort());
  3.         //最好情况下排序，时间复杂度是O(n)
  4.         int[] best = getArr();
  5.         Arrays.sort(best);
  6.         bestSort(best);
  7.     }

插入排序

插入排序的基本思想是将一个记录插入到有序表中，其实跟我们打牌时整理纸牌的顺序有点相似，假设第一张纸牌是有序的，将第二张与第一张有序的纸牌进行比较并整理，重复这个过程，将第三张纸牌与前两张进行比较寻找合适的位置插入，以此类推完成排序。

代码实现

  1. package com.learn.test.algorithm;
  3. /**
  4.  * 插入算法
  5.  * 比较像整理纸牌，是对未排序的数据，在有序队列中从后向前扫描找到合适位置插入。
  6.  *
  7.  * @author Bai
  8.  * @date 2021/8/22 13:53
  9.  */
  10. public class InsertionSort extends BaseSort {
  12.     /**
  13.      * 升序排序
  14.      *
  15.      * @param arr
  16.      */
  17.     @Override
  18.     void ascSort (int[] arr) {
  19.         if (null == arr || arr.length < 2) {
  20.             return;
  21.         }
  22.         for (int i = 1; i < arr.length; i++) {
  23.             for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
  24.                 swap(arr, j, j - 1);
  25.             }
  26.         }
  27.     }
  29.     @Override
  30.     void descSort (int[] arr) {
  31.         if (null == arr || arr.length < 2) {
  32.             return;
  33.         }
  34.         for (int i = 1; i < arr.length; i++) {
  35.             for (int j = i - 1; j >= 0 && arr[j] < arr[j + 1]; j--) {
  36.                 swap(arr, j, j + 1);
  37.             }
  38.         }
  39.     }
  41.     public static void main (String[] args) {
  42.         run(new InsertionSort());
  44.         //优化算法check
  45.         for (int i = 0; i < 100000; i++) {
  46.             int[] arr = getArr();
  47.             int[] clone = arr.clone();
  48.             ascSortOp(arr);
  49.             ascCheck(arr, clone);
  50.         }
  51.     }
  52. }

时间复杂度O(n²)&空间复杂度O(1)

插入排序跟冒泡算法一样，也是循环执行两次，它的复杂度也是O(n²)，因为没有使用额外的空间，所以空间复杂度也是O(n)。上面这一版的算法其实还是可以进行优化一下的， 现在执行过程中会进行很多次的交换增加了时复杂度，下面优化使用变量来替代swap()，减少时间复杂度。

  1. /**
  2.      * 算法优化
  3.      * 使用临时变量替代swap操作
  4.      *
  5.      * @param arr
  6.      */
  7.     public static void ascSortOp (int[] arr) {
  8.         if (null == arr || arr.length < 2) {
  9.             return;
  10.         }
  11.         for (int i = 1; i < arr.length; i++) {
  12.             //记录最左边需要交换的下标
  13.             int lastMinIndex = i;
  14.             for (int j = i - 1; j >= 0 && arr[i] < arr[j]; j--) {
  15.                 lastMinIndex = j;
  16.             }
  17.             if (lastMinIndex != i) {
  18.                 //交换i位置的数据到lastMinIndex位置，将lastMinIndex与i之间的数集体后移一位
  19.                 int tem = arr[i];
  20.                 for (int j = i; j > lastMinIndex; j--) {
  21.                     arr[j] = arr[j - 1];
  22.                 }
  23.                 arr[lastMinIndex] = tem;
  24.             }
  25.         }
  26.     }

选择排序

选择排序的思想很简单，就是每次在未排序的序列中找到最大或最小的值，放到序列的起始位置，接着继续在剩下未排序的序列中寻找最大或最小的值放到已排序序列的末尾，重复这个过程，直到完成排序。

代码实现

  1. package com.learn.test.algorithm;
  3. import java.util.Arrays;
  5. /**
  6.  * 选择排序
  7.  * 每次寻找未排序的数字中最小或最大的数值，放到未排序的数值首位或是末尾
  8.  *
  9.  * @author Bai
  10.  * @date 2021/8/22 13:20
  11.  */
  12. public class SelectionSort extends BaseSort {
  14.     /**
  15.      * 升序
  16.      */
  17.     @Override
  18.     void ascSort (int[] arr) {
  19.         if (null == arr || arr.length < 2) {
  20.             return;
  21.         }
  22.         for (int i = 0; i < arr.length - 1; i++) {
  23.             //每次循环之后最小值
  24.             int minIndex = i;
  25.             for (int j = i + 1; j < arr.length; j++) {
  26.                 minIndex = arr[j] < arr[minIndex] ? j : minIndex;
  27.             }
  28.             swap(arr, i, minIndex);
  29.         }
  30.     }
  32.     /**
  33.      * 降序
  34.      */
  35.     @Override
  36.     void descSort (int[] arr) {
  37.         if (null == arr || arr.length < 2) {
  38.             return;
  39.         }
  40.         for (int i = 0; i < arr.length - 1; i++) {
  41.             //每次循环之后最大值
  42.             int maxIndex = i;
  43.             for (int j = i + 1; j < arr.length; j++) {
  44.                 maxIndex = arr[j] > arr[maxIndex] ? j : maxIndex;
  45.             }
  46.             swap(arr, i, maxIndex);
  47.         }
  48.     }
  50.     /**
  51.      * 升序
  52.      */
  53.     public static void ascSortV2 (int[] arr) {
  54.         if (null == arr || arr.length < 2) {
  55.             return;
  56.         }
  57.         int end = arr.length - 1;
  58.         for (int i = 0; i < end; i++) {
  59.             //每次循环之后最小值
  60.             int minIndex = i;
  61.             int minMax = i;
  62.             for (int j = i + 1; j < end + 1; j++) {
  63.                 minIndex = arr[j] < arr[minIndex] ? j : minIndex;
  64.                 minMax = arr[j] > arr[minMax] ? j : minMax;
  65.             }
  66.             if (i == minMax && end == minIndex) {
  67.                 swap(arr, minIndex, minMax);
  68.             } else if (i == minMax) {
  69.                 swap(arr, end, minMax);
  70.                 if (i != minIndex) {
  71.                     swap(arr, i, minIndex);
  72.                 }
  73.             } else if (minIndex != minMax) {
  74.                 if (i != minIndex) {
  75.                     swap(arr, i, minIndex);
  76.                 }
  77.                 if (end != minMax) {
  78.                     swap(arr, end, minMax);
  79.                 }
  80.             }
  81.             end--;
  82.         }
  83.     }
  85.     public static void main (String[] args) {
  86.         run(new SelectionSort());
  87.         //同时找出 最大 最小 进行选择
  88.         v2();
  89.     }
  91.     private static void v2 () {
  92.         for (int i = 0; i < 100000; i++) {
  93.             //升序
  94.             int[] arr = getArr();
  95.             int[] arr1 = arr.clone();
  96.             ascSortV2(arr);
  97.             Arrays.sort(arr1);
  98.             check(arr, arr1);
  99.         }
  100.     }
  101. }

三种算法的区别

时间复杂度

从时间复杂度上来说三者的平均时间复杂度都是O(n²)，最坏的时间复杂度也是O(n²)，而冒泡和插入的最好时间复杂度则都是O(n²)

空间复杂度

三者的空间复杂度都是O(1)，没有使用额外的空间

稳定度

选择排序是不稳的，冒泡排序和插入排序是稳定的