Java基础算法-排序-二分插入排序

二分插入排序属于插入排序的一种

实现原理

其实二分插入排序的实现原理跟插入排序差不多，都是在一个数组里面，把第一个视为
有序的子序列，然后把后半部分视为无序的序列，后半部分就像从牌堆里面抓牌一样，
把循环到的元素按照有序的方式插入前面已经有序的子序列里面。
与直接插入排序区别就在寻找插入的位置的时候，使用了二分查找
来代替了从后向前遍历。从而减少搜索次数，

时间复杂度与稳定性

二分插入排序是一种稳定的排序算法，最好情况下的时间复杂度为O(N),最坏情况下的
时间复杂度为O(n^2),平均也为O(n^2)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
package zju.zsq.binarysort;
import org.junit.Test;
public class BinarySort {
	public  void binaryInsertSort(int[] data) {  
        for (int i = 1; i < data.length; i++) {  
            if (data[i] < data[i - 1]) {  
                // 缓存i处的元素值  
                int tmp = data[i];  
                // 记录搜索范围的左边界  
                int low = 0;  
                // 记录搜索范围的右边界  
                int high = i - 1;  
                while (low <= high) {  
                    // 记录中间位置  
                    int mid = (low + high) / 2;  
                    // 比较中间位置数据和i处数据大小，以缩小搜索范围  
                    if (data[mid] < tmp) {  
                        low = mid + 1;  
                    } else {  
                        high = mid - 1;  
                    }  
                }  
                //将low~i处数据整体向后移动1位  
                for (int j = i; j > low; j--) {  
                    data[j] = data[j - 1];  
                }  
                data[low] = tmp;  
                for (int number : data) {
    				System.out.print(number + " ");
    			}
    			System.out.println();
            }  
        }  
    }  
	
	@Test
	public void testBubbleSort() {
		int[] nums = { 1, 7, 3, 4, 5, 5, 9, 8, 11, 10 };
		binaryInsertSort(nums);
		System.out.println("排序之后：");
		for (int num : nums) {
			System.out.print(num + " ");
		}
	}
}
结果输出为：
1 3 7 4 5 5 9 8 11 10 
1 3 4 7 5 5 9 8 11 10 
1 3 4 5 7 5 9 8 11 10 
1 3 4 5 5 7 9 8 11 10 
1 3 4 5 5 7 8 9 11 10 
1 3 4 5 5 7 8 9 10 11 
排序之后:
1 3 4 5 5 7 8 9 10 11
Algorithms