二分插入排序


二分插入排序也叫折半插入排序,算法思想:

(1)计算 0 ~ i-1 的中间点,用 i 索引处的元素与中间值进行比较,如果 i 索引处的元素大,说明要插入的这个元素应该在中间值和刚加入i索引之间,反之,就是在刚开始的位置 到中间值的位置,这样很简单的完成了折半;

(2)在相应的半个范围里面找插入的位置时,不断的用(1)步骤缩小范围,不停的折半,范围依次缩小为 1/2 1/4 1/8 .......快速的确定出第 i 个元素要插在什么地方;

(3)确定位置之后,将整个序列后移,并将元素插入到相应位置。

代码实现(java):

	// 默认升序
	public void BinSort(int[] arr) {

		for (int i = 1; i < arr.length; i++) {

			int tmp = arr[i];
			int left = 0;
			int right = i - 1;

			while (left <= right) {
				int mid = (left + right) / 2;

				if (tmp > arr[mid]) {
					left = mid + 1;
				} else {
					right = mid - 1;
				}
			}

			for(int k = i; k > left; k--){
				arr[k] = arr[k-1];
			}
			
			arr[left] = tmp;
		}
	}

(二)算法复杂度

1.时间复杂度:O(n^2)

二分查找插入位置,因为不是查找相等值,而是基于比较查插入合适的位置,所以必须查到最后一个元素才知道插入位置。

二分查找最坏时间复杂度:当2^X>=n时,查询结束,所以查询的次数就为x,而x等于log2n(以2为底,n的对数)。即O(log2n)

所以,二分查找排序比较次数为:x=log2n

二分查找插入排序耗时的操作有:比较 + 后移赋值。时间复杂度如下:

1)最好情况:查找的位置是有序区的最后一位后面一位,则无须进行后移赋值操作,其比较次数为:log2n 。即O(log2n)

2)最坏情况:查找的位置是有序区的第一个位置,则需要的比较次数为:log2n,需要的赋值操作次数为n(n-1)/2加上 (n-1) 次。即O(n^2)

3)渐进时间复杂度(平均时间复杂度):O(n^2)

2.空间复杂度:O(1)

从实现原理可知,二分查找插入排序是在原输入数组上进行后移赋值操作的(称“就地排序”),所需开辟的辅助空间跟输入数组规模无关,所以空间复杂度为:O(1)


(三)稳定性

二分查找排序是稳定的,不会改变相同元素的相对顺序。




联系我们 | 友情链接