正文

折半插入排序学习笔记2006-10-23 22:51:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/wenzhuo316/19653.html

分享到:

 

  • 程序:

void BInsertSort(SqList &L)

 { // 对顺序表L作折半插入排序。算法10.2

   int i,j,m,low,high;

   for(i=2;i<=L.length;++i)

   {

     L.r[0]=L.r[i]; // L.r[i]暂存到L.r[0]

     low=1;

     high=i-1;

     while(low<=high)

     { // r[low..high]中折半查找有序插入的位置

       m=(low+high)/2; // 折半

       if LT(L.r[0].key,L.r[m].key)

         high=m-1; // 插入点在低半区

       else

         low=m+1; // 插入点在高半区

     }

     for(j=i-1;j>=high+1;--j)

       L.r[j+1]=L.r[j]; // 记录后移

     L.r[high+1]=L.r[0]; // 插入

   }

 }

  • 总结:此方法和直接插入排序所需的辅助空间相同,从时间上比较,仅减少了关键字比较的次数,记录的移动次数不变。所以,时间和空间复杂度都和直接插入排序相同。
  • 思想:在1到i-1的子序列中寻找插入的位置是采用折半查找。

阅读(3453) | 评论(1)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

loading...
您需要登录后才能评论,请 登录 或者 注册