vlambda博客
学习文章列表

插入排序

• 《算法导论》这本书介绍的第一个算法就是插入排序

• 插入排序与冒泡排序一样, 都是时间复杂度 O(n²)的排序算法

• 虽然时间复杂度是 O(n²) ,但JDK里实实在在是使用了它的

为什么JDK会用插入排序

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

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

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

实现

伪代码

INSERTION-SORT(A)
  for j=2 to A.length
    key = A[j]
    i = j - 1
    while i > 0 and A[i] > key
      A[i+1] = A[i]
      i = i - 1
    A[i+1] = key

Java实现

//排序最终数组从小到大排列
public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        //内循环保证了下标0~i之间的数都是已经排好序的(不包括i)
        for (int j = i; j > 0; j--) {
            if (arr[j] < arr[j - 1]) {
                //只要比前面的小就与前面的换位置
                swap(arr, j, j - 1); //swap函数自己实现一下吧
            } else {
                break;
            }
        }
    }
}

• 当数组已经有序的情况, 对插入排序是最好情况, 插入排序的时间复杂度为O(n);
• 空间复杂度O(1)