插入排序之折半插入排序

由于插入排序的基本思想是在一个有序序列中插入一个新的记录，则可以利用"折半查找"查询插入位置，由此得到的插入排序算法为"折半插入排序"。算法如下：

<pre name="code" class="cpp">void BInsertSort () {　　// 对顺序表L作折半插入排序　　for ( i=2; i<=length; ++i ) 　　{　　　 r[0] = r[i];　　　　　　　　　　　　　　// 将L.r[i]暂存到L.r[0]　　　 low = 1; high = i-1;　　　 while (low<=high) 　　　 { 　　　　　　　　　　　// 在r[low..high]中折半查找有序插入的位置　　　　m = (low+high)/2; 　　　　　　　　　　　　// 折半　　　　if (r[0] < r[m]) high = m-1; 　// 插入点在低半区　　　　else low = m+1; 　　　　　　　　　　　　　// 插入点在高半区　　　 } // while　　　 for ( j=i-1; j>=low; –j ) r[j+1] = r[j]; // 记录后移　　　r[high+1] = r[0];　　　　　　　　　　　　// 插入　 }} // BInsertSort

　　但是，折半插入排序只能减少排序过程中关键字比较的时间，并不能减少记录移动的时间，因此折半插入排序的时间复杂度仍为O (n2)。

你不怕困难，困难就怕你。

相关文章：

你感兴趣的文章：

标签云：