文档章节

二分插入排序

风中的树叶
 风中的树叶
发布于 2013/06/25 23:56
字数 379
阅读 1762
收藏 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

没有更多内容

加载失败,请刷新页面

加载更多

深入解析ES6之数据解构的用法

本文介绍了深入理解ES6之数据解构的用法,写的十分的全面细致,具有一定的参考价值,对此有需要的朋友可以参考学习下。如有不足之处,欢迎批评指正。 一 对象解构 对象解构语法在赋值语句的左...

前端攻城老湿
6分钟前
0
0
芯片原理和量子力学

很多文盲觉得量子力学只是一个数学游戏,没有应用价值,呵呵,下面咱给计算机芯片寻个祖宗,请看示范: 导体,咱能理解,绝缘体,咱也能理解,小盆友们第一次被物理整懵的,怕是半导体了,所...

天王盖地虎626
6分钟前
0
0
Django model update的各种用法介绍

Django model update的各种用法介绍 model update常规用法 假如我们的表结构是这样的: class User(models.Model): username=models.CharField(max_length=255,unique=True,verbose_na......

_Change_
9分钟前
1
0
Frost & Sullivan权威报告:阿里云再次领跑云WAF大中华区市场

近日,国际权威分析机构Frost & Sullivan 针对Web应用防火墙(简称“WAF”)领域发布了《2017年亚太区Web应用防火墙市场报告》,阿里云以市场占有率45.8%的绝对优势连续两年领跑大中华区云WAF...

阿里云官方博客
14分钟前
0
0
Java程序员可知为何公司宁花25K重新招人,也不花20K留住老员工?

身在职场,经常会暗自打听同事工资,尤其是得知身边新入职同事的工资居然比自己高,还高出一大截时,心里自然很不平衡,一心想要离职。 那么,为什么公司宁愿花高价招聘新员工也不愿意给老员...

Java填坑路
20分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部