【模板小程序】二分法插入排序

Java版源程序来自:http://www.cnblogs.com/PerkinsZhu/p/5674572.html,在此感谢。

 1 #include <iostream>
 2 #include <vector>
 3 #include <string>
 4 using namespace std;
 5 
 6 void printArray(string str,vector<int>& array){
 7     cout<<str;
 8     for(int val:array){
 9         cout<<val<<" ";
10     }
11     cout<<endl;
12 }
13 
14 void binaryInsertionSort(vector<int>& array) {
15     printArray("原数组:", array);
16     int time=0;
17     for (int i = 1; i < (int)array.size(); ++i) {
18         int temp = array[i];
19         int right = i - 1;
20         int left = 0;
21         int mid;
22         // 定位
23         while (left <= right) {
24             //mid = (left + right) / 2;
25             mid = left+(right-left)/2;
26             if (array[mid] > temp) {
27                 right = mid - 1;
28             } else if (array[mid] < temp) {
29                 left = mid + 1;
30             }
31         }
32         // 移动数组
33         for (int j = i; j > left; j--) {
34             array[j] = array[j - 1];
35         }
36         // 在找到的位置插入
37         array[left] = temp;
38         printArray("第" + to_string(++time) + "次循环排序结果: ", array);
39     }
40 }
41 
42 int main()
43 {
44     vector<int> v={21,8,2,18,0,9,27,12,5,24};
45     binaryInsertionSort(v);
46     return 0;
47 }

运行结果:

原数组:21 8 2 18 0 9 27 12 5 24 第1次循环排序结果: 8 21 2 18 0 9 27 12 5 24 第2次循环排序结果: 2 8 21 18 0 9 27 12 5 24 第3次循环排序结果: 2 8 18 21 0 9 27 12 5 24 第4次循环排序结果: 0 2 8 18 21 9 27 12 5 24 第5次循环排序结果: 0 2 8 9 18 21 27 12 5 24 第6次循环排序结果: 0 2 8 9 18 21 27 12 5 24 第7次循环排序结果: 0 2 8 9 12 18 21 27 5 24 第8次循环排序结果: 0 2 5 8 9 12 18 21 27 24 第9次循环排序结果: 0 2 5 8 9 12 18 21 24 27

二分查找就是把插入位置的寻找过程由原来的顺序查找改成了二分查找,效率很高。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Kevin-ZhangCG

[ Java面试题 ] 集合篇

21170
来自专栏云霄雨霁

查找----基于有序数组

18200
来自专栏拭心的安卓进阶之路

Java 集合深入理解(5):AbstractCollection

今天好累,来学学 AbstractCollection 吧! ? 什么是 AbstractCollection AbstractCollection 是 Ja...

22590
来自专栏Golang语言社区

Go 语言数据类型

在 Go 编程语言中,数据类型用于声明函数和变量。 数据类型的出现是为了把数据分成所需内存大小不同的数据,编程的时候需要用大数据的时候才需要申请大内存,就可以充...

32670
来自专栏用户3030674的专栏

约瑟夫环(排成圈)

/** * 约瑟夫环问题主要是考虑下标问题,只要解决了下标控制问题,这个题目就不难了 * 在这里我是分成了3中情况: * 1,下标小于剩余人数时:删...

11120
来自专栏Android开发指南

12:集合map、工具类

37180
来自专栏风口上的猪的文章

.NET面试题系列[11] - IEnumerable<T>的派生类

ICollection<T>继承IEnumerable<T>。在其基础上,增加了Add,Remove等方法,可以修改集合的内容。IEnumerable<T>的直...

12520
来自专栏章鱼的慢慢技术路

顺序表示的线性表——顺序表

25240
来自专栏一“技”之长

Swift讲解专题五——集合类型 原

        Swift中提供了3种集合类型,Array数据类型,Set集合类型,Dictionary字典类型。Array用于存放一组有序的数据,数据角标从0...

9130
来自专栏AILearning

Map集合

Collection |--List:元素是有序的,元素可以重复,因为该集合体系有索引 |--ArrayList:底层的数据结构使用的是数据结构。特点:查询...

25160

扫码关注云+社区

领取腾讯云代金券