Sorting Algorithms:Binary Insertion Sort
前言
该博客用于本弱鸡复习巩固, 打牢基础, 还望各大佬不吝赐教.
基本思路
二分插入排序, 改进插入直接插入排序
在新元素插入到已序数组时, 用二分法查找插入的位置
算法复杂度分析
最坏 | 最好 | 稳定性 | 空间复杂度 |
---|---|---|---|
O(n^2) | O(nlog2n) | 稳定 | O(1) |
p.s.
最好情况: 每次插入的位置 k 都是已序数组的最后的位置, 则无需再执行移位赋值操作 O(n*log2n)
最坏情况: 每次插入的位置 k 都是已序数组的最前的位置, 则整个已序数组需要移位赋值 O(n^2)
二分查找时间复杂度 O(log2n)
代码实现
- import java.util.Arrays;
- import java.util.Random;
- /**
- * 二分插入排序, 改进插入直接插入排序
- * 在新元素插入到已序数组时, 用二分法查找插入的位置
- * 最好情况: 每次插入的位置 k 都是已序数组的最后的位置, 则无需再执行移位赋值操作 O(n*log2n)
- * 最坏情况: 每次插入的位置 k 都是已序数组的最前的位置, 则整个已序数组需要移位赋值 O(n^2)
- * 空间复杂度 O(1)
- * 稳定性 稳定
- * 二分查找时间复杂度 O(log2n)
- * @author Wayne Zhang
- * @date 2018/07/17
- */
- public class BinaryInsertion {
- public static void main(String[] args) {
- int[] a = new int[10];
- //random array
- for (int i = 0; i < a.length; i++) {
- Random rd = new Random();
- a[i] = rd.nextInt(10);
- }
- System.out.println("Random Array :");
- System.out.println(Arrays.toString(a));
- System.out.println();
- System.out.println("Binary Insertion Sort :");
- // 插入排序
- // 外循环规定从第二个元素开始, 将元素插入到已排好的数组中
- for (int i = 1; i < a.length; i++) {
- // 得到插入的位置
- int k = findByBinary(a, i);
- // 保存 a[i]
- int key = a[i];
- // 元素后移
- for (int j = i - 1; j >= k; j--) {
- a[j + 1] = a[j];
- }
- a[k] = key;
- }
- System.out.println(Arrays.toString(a));
- }
- public static int findByBinary(int[] a, int i) {
- int highIndex = i - 1;
- int lowIndex = 0;
- int mid = -1;
- while (lowIndex <= highIndex) {
- mid = (highIndex + lowIndex) / 2;
- if (a[i] >= a[mid]) {
- // 若相等, 保证新元素插在旧元素后面
- lowIndex = mid + 1;
- } else {
- highIndex = mid - 1;
- }
- }
- return lowIndex;
- }
- }
复制代码
参考
大话数据结构:https://book.douban.com/subject/6424904/ https://book.douban.com/subject/6424904/
来源: https://juejin.im/post/5b4efbc1f265da0fa42cd2b3