折半插入排序

(一) 算法描述

折半插入排序是直接插入排序的一种优化，在直接插入排序中待排序的元素需要与有序数列的每个元素从后往前逐个进行比较，直接插入排序对基本有序数列具有很高的排序效率，但是当乱序情况下，其比较次数会很多。折半插入排序在直接排序的基础上在位置查找部分采用折半（二分查找）算法进行插入位置的确定，进而节省查找时间。

(二) 算法分析

最差时间复杂度：\(O(n^2)\)

最好时间复杂度：\(O(nlogn)\)

平均时间复杂度：\(O(n^2)\)

空间复杂度：　　\(O(1)\)

稳定性：　　　　稳定

(三) 算法伪码

INSERTION-SORT(A)
for j=2 to A.length
	key = A[j]
	//Insert A[j] into the sorted sequence A[1..j-1].
	left = 0
	right = i-1
	while left <= right // 采用二分法定位新牌的位置
		mid = (left+right)/2
		
		if A[mid] > key
			right = mid - 1
		else 
			left = mid + 1
		
	for j=i-1 to left	// 将欲插入新牌位置右边的牌整体向右移动一个单位
		A[j+1] = A[j]
	
	A[left] = key		// 将抓到的牌插入手牌

(四) 算法步骤

缓存当前要排序的元素的值，以便找到正确的位置进行插入；

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

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

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

(五) java实现

/**
 * 折半插入排序
 *
 * @author tonysu,
 * @version 1.0v.
 * @Create 2017/11/12 下午9:13,
 */
public class BinaryInsertSort{

    /**
     * 排序函数
     *
     * @param data  输入数组
     * @param order 排序方式：
     *              true为升序
     *              false为降序
     * @return
     */
    public int[] sort(int[] data, boolean order){

        if(data.length == 0 || data == null){
            throw new NullPointerException("数组为空");
        }

        if(data.length == 1){
            return data;
        }

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

            int key = data[i];
            int left = 0;
            int right = i - 1;
            if(order){
                while(left <= right){
                    int mid = (left+right)/2;
                    if(data[mid] > key){
                        right = mid - 1;
                    }else{
                        left = mid + 1;
                    }
                }

            }else{
                while(left <= right){
                    int mid = (left+right)/2;
                    if(data[mid] < key){
                        right = mid - 1;
                    }else{
                        left = mid + 1;
                    }
                }
            }

            for(int j=i-1; j>=left; j--){
                data[j+1] = data[j];
            }

            data[left] = key;

        }

        return data;
    }
}

(六) python实现

class InsertSort(object):

    """折半插入排序类"""
    def __init__(self):
        super(InsertSort, self).__init__()

    def sort(self, datas, order):
        """对传入的数值数组datas进行折半插入排序.

          Args:
            datas: 待排序数值数组 e.g. [12, 3, 24, 11, 34, 33, 42, 9, 4]
            order: 排序顺序 e.g. True为升序， False为降序

          Returns:
            datas: 排好序的数值数组.
          """

        for i in range(1, len(datas)):
            left = 0
            right = i-1
            key = datas[i]
            if order:
                while left <= right:
                    mid = (left + right)/2
                    if datas[mid] > key:
                        right = mid - 1
                    else:
                        left = mid + 1
            else:
                while left <= right:
                    mid = (left + right)/2
                    if datas[mid] < key:
                        right = mid - 1
                    else:
                        left = mid + 1

            for j in range(i-1, left-1, -1):
                datas[j+1] = datas[j]

            datas[left] = key
        return datas


def main():

    data = [12, 3, 24, 11, 34, 33, 42, 9, 4]
    print data
    order = True
    insert_sort = InsertSort()
    result = insert_sort.sort(data, order)
    print result


if __name__ == '__main__':
    main()

(七) 算法优缺点

1. 优点

相对于直接插入排序比较次数少，查找速度快，平均性能好；

2. 缺点

要求待查表为有序表；

插入删除困难：因为折半查找法要求待查表为有序表，所以在插入的时候你就不能随便插入了。你必须找到待插入的元素在表中的位置才可以插入，所以插入的时候比较麻烦。

(八) 总结

当n较大时，二分插入排序的比较次数比直接插入排序的最差情况好得多，但比直接插入排序的最好情况要差，所当以元素初始序列已经接近升序时，直接插入排序比二分插入排序比较次数少。二分插入排序元素移动次数与直接插入排序相同，依赖于元素初始序列。

如果比较操作的代价比交换操作大的话可以采用二分插入排序。

参考博客

插入排序及优化

排序算法之二分法（折半）插入排序算法

排序算法总结

常用排序算法总结(一)