文档章节

二分插入排序

风中的树叶
 风中的树叶
发布于 2013/06/25 23:56
字数 379
阅读 1759
收藏 5

    二分插入排序也称折半插入排序,基本思想是:设数列[0....n]分为两部分一部分是[0...i]为有序序列,另一部分是[i+1.....n]为无序序列,从无序序列中取一个数 x ,利用二分查找算法找到 x 在有序序列中的插入位置并插入,有序序列还是有序的,接下来重复上述步骤,直到无序序列全部插入有序序列 ,这是整个序列只剩下有序序列即有序了。

 

void  BinaryInsertSort(int *pArray, int len)
{
  //刚开始设有序序列只有一个元素 pArray[0],无序序列为[1...n]了
  for( int i = 1; i < len; i++)
  {
     //无序序列元素与有序序列比较(从有序列最后一个元素往前比较)
     if(pArray[i] >= pArray[i - 1])
     {
       continue;
     }
     //当无序序列元素比有序序列最后一个元素小时,利用二分查找法在有序序列中查找插入位置
     int low = 0; 
     int high = i - 1;
     int mid = 0;
     int temp = pArray[i];
     while(low <= high)
     {
       mid = (low + high) / 2;
       if(temp >= pArray[mid])
       {
          low = mid + 1;
       }
       else //(temp < pArray[mid])
       {
          high = mid - 1;
       }
     }
     //low位置就是要插入的位置,所以low到i之间的元素都需要往后移动一个位置
     int j = i;
     while(j > low)
     {
       pArray[j] = pArray[j - 1];
       j--;
     }
     //把无序序列中的pArray[i]放到有序序列中low的位置,这样就完成了无序序列 i 位置的数插入了有序序列中
     pArray[low] = temp;
  }

}

© 著作权归作者所有

共有 人打赏支持
上一篇: 直接插入排序
下一篇: 冒泡排序
风中的树叶
粉丝 1
博文 15
码字总数 2682
作品 0
深圳
高级程序员
私信 提问
常用基础排序算法

首先初始化了一个MAX大小的数组,用乱序函数将数组打乱,用于测试各个排序函数,先附上要测试的几个基础排序函数,后面附上乱序函数和主调度函数。代码就那么几行,只是注释的思乱占了比较多...

穿靴子的猫LJL
2015/10/13
11
0
排序算法:二分排序(插入排序+二分查找)

插入排序就是一直向后读,第一个数,加入前面已经有序的一串数里。 而插入排序是笨笨的一个个向前找的,可以优化一下,用二分查找找到合适的位置。 插入排序代码 void Insertsort2(int a[], ...

qq_36523667
03/03
0
0
直接插入排序以及其改进版-二分法排序

插入排序是一种简单直观的排序算法。序列可以分为有序区和无序区,开始时有序区只有第一个元素,然后每次把无序区中第一个元素插入到有序区中。 当无序区为空时,排序结束。 那如何把元素插入...

realsa
2016/10/10
24
0
java算法篇总结

冒泡排序 比较相邻元素,如果第一个比第二个大,那么交换他们的位置;每对相邻元素进行依次比较,最后的元素应该是最大的。 选择排序 寻找最小值所在索引位置,于i当前起始点进行对调位置 pu...

丛林迷雾
2015/09/07
82
0
[LeetCode] Count of Smaller Numbers After Self 计算后面较小数字的个数

You are given an integer array nums and you have to return a new counts array. The counts array has the property where is the number of smaller elements to the right of . Exampl......

机器的心脏
2017/12/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

nuc970 uboot nand-boot,kernel, filesystem 烧录位置

一 烧写到Nand Flash **1.1 **相关文件说明 l BSP版本:nuc970bsp-release-20150519.zip l NuWriter版本:2015/04/28-V01,nuvoTon Nu-Writer V1.0 l 烧写文件: u-boot-spl.bin:负责将u-b......

CookieDemo
44分钟前
1
0
python中sort和sorted函数小结

L.sort(cmp=None, key=None, reverse=False) sorted(iterable, cmp=None, key=None, reverse=False) 这样看,sorted函数只比sort函数多一个iterable参数,其余没什么不同,iterable是一个迭代......

上官夏洛特
今天
3
0
thinkphp 常用SQL执行语句总结

第一条:Db::tablera('vr_panomas')->where(['delete_time'=>0,'id'=>['in',$pids]])->field(['id'=>'id','post_thumb'=>'thumb','post_title'=>'title','post_tags'=>'tags','post_price'=>......

koothon
今天
4
0
支付宝返回状态resultStatus意思

上一篇集成支付宝的时候,会有一些支付宝返回的resultStatus,具体意思是: 9000 订单支付成功 8000 正在处理中 4000 订单支付失败 6001 用户中途取消 6002 网络连接出错 还有memo,意思就是...

RainOrz
今天
3
0
electron webview 页面加载事件顺序

1.did-start-loading 页面开始加载 2.load-commit 主页面文档加载 3.page-title-updated title 4.dom-ready 主页面 dom 加载完成 5.load-commit frame文档加载 6.did-frame-finish-load fram......

dubox
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部