首页 > 代码库 > 内部排序(3)——插入排序之折半插入排序

内部排序(3)——插入排序之折半插入排序

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

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

  可是。折半插入排序仅仅能降低排序过程中keyword比較的时间,并不能降低记录移动的时间,因此折半插入排序的时间复杂度仍为O (n2)。

内部排序(3)——插入排序之折半插入排序