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;
}
}
