插入排序

  • 《算法导论》这本书介绍的第一个算法就是插入排序
  • 插入排序与冒泡排序一样, 都是时间复杂度 O(n²)的排序算法
  • 虽然时间复杂度是 O(n²) ,但JDK里实实在在是使用了它的

image.png

为什么JDK会用插入排序

为什么JDK这么追求效率,却还使用了时间复杂度较高的插入排序?

时间复杂度主要是衡量当输入增加的时候, 算法耗时的增长趋势, 记住只是趋势
但如果需要处理的数组很小呢? 那插入排序的优势就会体现出来, 虽然复杂度高, 但是在小规模的数组排序中表现效率还是非常好的
image.png

  • 在JDK实现的排序代码中当元素小于7个的时候, 就会使用插入排序

实现

伪代码

  1. INSERTION-SORT(A)
  2.   for j=2 to A.length
  3.     key = A[j]
  4.     i = j - 1
  5.     while i > 0 and A[i] > key
  6.       A[i+1] = A[i]
  7.       i = i - 1
  8.     A[i+1] = key

Java实现

  1. //排序最终数组从小到大排列
  2. public static void insertionSort(int[] arr) {
  3.     for (int i = 1; i < arr.length; i++) {
  4.         //内循环保证了下标0~i之间的数都是已经排好序的(不包括i)
  5.         for (int j = i; j > 0; j--) {
  6.             if (arr[j] < arr[j - 1]) {
  7.                 //只要比前面的小就与前面的换位置
  8.                 swap(arr, j, j - 1); //swap函数自己实现一下吧
  9.             } else {
  10.                 break;
  11.             }
  12.         }
  13.     }
  14. }
  • 当数组已经有序的情况, 对插入排序是最好情况, 插入排序的时间复杂度为O(n);
  • 空间复杂度O(1)