-折半插入算法介绍
折半插入排序
如果线性表是有序的,进行查找可以用折半查找来实现。在确定出待插入位置后,就可以统一的向后移动元素了。
|
|
从上述算法中,不难看出折半插入排序仅仅是减少了比较元素的次数,约为O(nlog2n),该比较次数与待排序表的初始状态无关,仅取决于表中元素个数n;而元素的移动次数没有改变,它取决于待排序表的初始状态。因此,折半插入排序的时间复杂度仍为O(n2)
作死のBlog
-折半插入算法介绍
折半插入排序
如果线性表是有序的,进行查找可以用折半查找来实现。在确定出待插入位置后,就可以统一的向后移动元素了。
|
|
从上述算法中,不难看出折半插入排序仅仅是减少了比较元素的次数,约为O(nlog2n),该比较次数与待排序表的初始状态无关,仅取决于表中元素个数n;而元素的移动次数没有改变,它取决于待排序表的初始状态。因此,折半插入排序的时间复杂度仍为O(n2)
WeChat Pay
Alipay