排序算法:二分插入排序

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/