=================
== Time Stream ==
=================
一个小学生

算法之直接插入排序学习

直接插入排序算法重新学习。

插入排序可以类比打扑克牌时整理扑克牌顺序的场景,插入排序算法的思想是:将待排序的序列分为两段,前面一段是排序好的序列,后面一段是未排序的序列,每次只拿一个元素,将这个元素按照其值的大小插入到前面一段已经排序好的序列中去。

插入排序算法有以下几种:

  • 直接插入排序
  • 二分插入排序
  • 希尔排序

直接插入排序算法

  1. 假设有个线性序列为:${a_0, a_1, …, a_{i-1}, a_i, …, a_{n-1}}$,在第i(i1 <= i < n)次拿出一个元素$a_i$进行处理的时候,前i个元素组成的序列是排序好的序列:${a_0, a_1, …, a_{i-1}}$,后面的元素是未排序的序列${a_i, …, a_{n-1}}$,此时需要把$a_i$插入到排序好的序列中去,插入完成时,前面的序列仍然是排序好的。
  2. 一直重复执行步骤1,直到所有都排序好。

直接插入排序代码示例

/**
 * 直接插入排序
 */
public class InsertionSort {

    /**
     * 直接插入排序
     * @param source 待排序的数组
     */
    public void insertionSort(Integer[] source) {
        /**
         * 从索引位置位1的地方开始循环待排序数组,这里是将数组分为两部分:
         * 索引位置为0的是当做前半部分已经排序的序列,从索引位置为1的开始
         * 当做是后半部分未排序的序列。
         */
        for (int i = 1; i < source.length; i++) {
            // 从后半部分未排序的序列中取出第一个元素
            Integer temp = source[i];
            int j = 0;
            /**
             * 从已排序的最后一个元素开始往前遍历,并和从后半部分未排序的
             * 序列中取出的第一个元素source[i]进行比较,如果已排序的元素比未排
             * 序的元素大,就将已排序序列中这个元素往右边移动一位,接续往已排序的
             * 序列左边进行比较;如果遇到了已排序的元素比未排序的元素小或者相等,
             * 说明未排序这个元素找到了位置,就将这个未排序的元素插入到该位置处即可
             */
            for (j = i - 1; j >= 0 && source[j] > temp; j--) {
                source[j + 1] = source[j];
            }
            source[j + 1] = temp;
        }
    }

    public static void main(String[] args) {
        Integer[] array = new Integer[] {3, 4, 6, 2, 3, 1, 4, 10, 48, 2, 3, 12, 14};
        new InsertionSort().insertionSort(array);
        System.out.println(Arrays.toString(array));
    }
}

直接插入排序算法分析

时间复杂度

  • 最好情况,是个已经排序好的序列,时间复杂度为O(n)
  • 最坏情况,是个逆序排列的序列,时间复杂度为$O(n^2)$
  • 平均情况,时间复杂度为$O(n^2)$

空间复杂度

算法中使用一个temp变量占用一个存储单元,空间复杂度为O(1)

算法的稳定性

在直接插入排序算法中,相等的元素比较后,不会改变它们原有次序,因此直接插入排序算法是稳定的。

适用场景

  • 直接插入排序不适用与元素过多的场景,因为需要移动元素
  • 直接插入排序适用于元素基本有序的场景,基本有序的情况下排序时间复杂度接近O(n)

优化

算法中在前面一段的有序序列中进行查找的时候,采用的是顺序查找的算法,这里可以进行优化。由于前面部分序列使用的是顺序存储且是排序好的,可以使用二分查找代替顺序查找提高效率,这样的排序称为二分插入排序。

参考内容

  • 《数据结构(Java版)》