算法之二分插入排序学习
二分插入排序算法重新学习。
插入排序可以类比打扑克牌时整理扑克牌顺序的场景，插入排序算法的思想是：将待排序的序列分为两段，前面一段是排序好的序列，后面一段是未排序的序列，每次只拿一个元素，将这个元素按照其值的大小插入到前面一段已经排序好的序列中去。
插入排序算法有以下几种：
- 直接插入排序
- 二分插入排序
- 希尔排序
二分插入排序算法
在直接插入排序算法中，在前半部分已排好序的序列中进行查找的时候，是顺序查找。这部分数据是顺序存储且排序好的，因此可以使用二分查找来进行优化。
二分插入排序代码示例
/**
* 二分插入排序
*/
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版）》