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

算法之二分插入排序学习

二分插入排序算法重新学习。

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

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

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

二分插入排序算法

在直接插入排序算法中,在前半部分已排好序的序列中进行查找的时候,是顺序查找。这部分数据是顺序存储且排序好的,因此可以使用二分查找来进行优化。

二分插入排序代码示例

/**
 * 二分插入排序
 */
public class InsertionSort {

    public void insertionSort(Integer[] source) {

        for (int i = 1; i < source.length; i++) {
            Integer temp = source[i];

            int left = 0;
            int right = i - 1;

            while (left <= right) {
                int mid = (left + right) >>> 1;
                if (temp > source[mid]) {
                     left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

            // left到i - 1之间的元素要往右边移动
            for (int j = i - 1; j >= left; j--) {
                source[j + 1] = source[j];
            }

            source[left] = 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(log_2n)$
  • 最坏情况,是个逆序排列的序列,时间复杂度为$O(n^2)$
  • 平均情况,时间复杂度为$O(n^2)$

空间复杂度

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

算法的稳定性

二分插入排序算法是稳定的。

适用场景

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

参考内容

  • 《数据结构(Java版)》