文档章节

二分插入排序

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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

windbg调试C源码级驱动

联机方式不多说了。我博客里有,英文的。 windbg联机文档 https://docs.microsoft.com/zh-cn/windows-hardware/drivers/debugger/debug-universal-drivers---step-by-step-lab--echo-kernel......

simpower
32分钟前
0
0
redis快照和AOF简介

数据持久化到硬盘:一是快照(snapshotting),二是只追加文件(append-only file AOF) 快照 核心原理:redis某个时间内存内的所有数据写入硬盘 场景:redis快照内存里面的数据 1. 用户发送bgsav...

拐美人
33分钟前
0
0
这个七夕,送你一份程序员教科书级别的告白指南

给广大爱码士们的高能预警: 今天,就是七夕了…… (单身非作战人群请速速退场!) 时常有技术GG向个推君抱怨 经过网民多年的教育 以及技术人持之以恒的自黑 冲锋衣狂热分子·格子衫骨灰级粉...

个推
38分钟前
0
0
python爬虫日志(15)cookie详解

转载:原文地址 早期Web开发面临的最大问题之一是如何管理状态。服务器端没有办法知道两个请求是否来自于同一个浏览器。那时的办法是在请求的页面中插入一个token,并且在下一次请求中将这个...

茫羽行
39分钟前
0
0
qlv视频格式转换器

  腾讯视频中的视频影视资源有很多,小编经常在里面下载视频观看,应该也有很多朋友和小编一样吧,最近热播的电视剧也不少,如《香蜜沉沉烬如霜》、《夜天子》还有已经完结的《扶摇》,这么...

萤火的萤火
42分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部