文档章节

二分插入排序

风中的树叶
 风中的树叶
发布于 2013/06/25 23:56
字数 379
阅读 1.8K
收藏 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
深圳
高级程序员
私信 提问
加载中

评论(0)

数据结构图文解析之:直接插入排序及其优化(二分插入排序)解析及C++实现

0. 数据结构图文解析系列 数据结构系列文章 数据结构图文解析之:数组、单链表、双链表介绍及C++模板实现 数据结构图文解析之:栈的简介及C++模板实现 数据结构图文解析之:队列详解与C++模板...

good luck.
2016/02/17
0
0
入门算法-二分查找,二分排序,插入排序,冒泡排序

1.二分查找(时间复杂度O(lgn)) 二分查找,需要将业务模拟一个有序数组。然后查找某个值在该数组中的位置。 二分查找的关键是: 1)查找的值一定在某次的范围中间。即使值是最后一个,也要按...

osc_edtw4h1l
2019/09/16
1
0
数据结构图文解析之:二分查找及与其相关的几个问题解析

0. 数据结构图文解析系列 数据结构系列文章 数据结构图文解析之:数组、单链表、双链表介绍及C++模板实现 数据结构图文解析之:栈的简介及C++模板实现 数据结构图文解析之:队列详解与C++模板...

good luck.
2016/02/17
0
0
排序算法:冒泡排序、选择排序、插入排序、快速排序、希尔排序,以及二分查找。

排序算法: 稳定排序:两个相等的元素不会交换位置 。 1、冒泡排序:时间复杂度 O(n2),相同元素的前后顺序不会改变,冒泡排序是一种稳定排序算法。 代码实现: public static void bubbl...

osc_i5rnp27q
2019/10/14
2
0
优化的直接插入排序(二分查找插入排序,希尔排序)

本博文向大家介绍了插入排序的三种实现:直接插入排序,二分查找插入排序,希尔排序。详细分析的其实现过程、时间复杂度和空间复杂度、稳定性以及优化改进策略。最后简单的做了下性能测试。 ...

滴答的雨
2014/07/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

SpringBoot 整合 Redis 缓存

1.首先导入使用Maven导入jar包 <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-data-redis</artifactId></dependency><......

FH-Admin
29分钟前
12
0
如何安装WordPress插件 - 初学者的分步指南 - WP站长

<!-- wp:paragraph -->安装WordPress后,每一个初学者需要学习的第一件事就是如何安装WordPress插件。插件允许您向WordPress添加新功能,例如添加图库、幻灯片等。有数千个可用于WordPress的...

wpzhanzhang
44分钟前
8
0
【Flutter组件终结篇】332个组件 658页PDF

老孟导读:历时1年的时间,整理完成了330+组件的详细用法,不仅包含UI组件,还包含了功能性的组件。 虽然整理了 330+的组件基本用法,但并不是让你每一个都学习一遍,任何技术基本都是掌握 ...

老孟Flutter
今天
17
0
三星手机又中招:一张壁纸可引发系统崩溃 附临时解决方法

  前几天国内有大量用户发现三星手机崩溃、黑屏或者无限重启, 这可能是三星手机的日历 APP 的 bug。这件事还没完,三星手机今天又发现了新的问题,换上一张特别的壁纸就会导致系统崩溃,不...

alkcendkljk
今天
13
0
查找当前目录和文件目录[重复] - Find current directory and file's directory [duplicate]

问题: This question already has answers here : 这个问题已经在这里有了答案 : How to properly determine current script directory? 如何正确确定当前脚本目录? (11 answers) (11个答...

技术盛宴
今天
27
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部