【408数据结构与算法】—折半插入排序（十六）
折半插入排序
折半插入排序:查找插入位置时采用折半查找法
算法描述
算法分析
- 折半查找要比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快。
- 它所需要的关键码比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数，在插入第i个对象时，需要经过[log2i]+1次关键码比较，才能确定它应插入的位置
- 当n较大的时候，总关键码比较的次数比直接插入排序的最坏情况要好得多，但比其最好的情况要差
- 在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比折半插入排序执行的关键码比较次数要少
折半插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列
- 减少了比较次数，但是没有减少移动的次数
- 平均性能优于直接插入排序
