一般的插入排序方法想必大家都写过,基础好的几分钟就可以写出来了,基础差一点的调一调也就出来了。
下面是一般通用的插入排序算法:
#include<iostream>
using namespace std;
const int SIZE = 10;
int arrs[SIZE];
//打印排序后的数组
void printArr(){
for(int i = 0; i < SIZE; i ++){
cout<<arrs[i]<<(i==SIZE-1?"":" ");
}
cout<<endl;
}
//初始化数组
void initArr(){
for(int i = 0; i < SIZE; i++){
arrs[i] = rand()%50; //产生随机数
}
printArr();
}
//排序函数
void insertSort(){
int temp,i,j;
for(i = 1; i < SIZE; i ++){
temp = arrs[i];
j = i - 1;
if(temp < arrs[j]){
for(; temp < arrs[j]; j --){
arrs[j+1] = arrs[j];
}
arrs[j+1] = temp;
}
}
}
int main()
{
initArr();
insertSort();
printArr();
return 0;
}
其实插入排序还有其它几种算法:二分插入排序 、双路径插入排序。虽然写法不同,但时间复杂度是一样的。
下面就讲 二分插入排序。思想很简单,就是在插入排序时应用二分法来把当前元素和已经排好序的比较。
#include<iostream>
using namespace std;
const int SIZE = 10;
int arr2[SIZE];
//初始化数组,数字随机产生
void initArr(){
for(int i = 1; i <= SIZE; i ++){
arr2[i] = rand()%50;
}
}
//打印数组
void printArr(){
for(int i = 1; i <= SIZE; i ++){
cout<<arr2[i]<<(i == SIZE?"":" ");
}
cout<<endl;
}
//二分插入法
void bInsert(){
int i,j,high,low,mid,temp;
for(i = 2; i <= SIZE; i ++){
temp = arr2[i];
low = 1;
high = i - 1;
while(low <= high){
mid = (low + high) / 2;
if(temp > arr2[mid])
low = mid + 1;
else
high = mid - 1;
}//while
for(j = i - 1; j >= high+1; --j)
arr2[j+1] = arr2[j];
arr2[j+1] = temp;
} //for
}
int main()
{
initArr();
printArr();
bInsert();
printArr();
return 0;
}
分享到:
相关推荐
另一种是按列排列, 即放完一列之后再顺次放入第二列。在C语言中,二维数组是按行排列的。 在图4.1中,按行顺次存放,先存放a[0]行,再存放a[1]行,最后存放a[2]行。每行中有四个元素也是依次存放。由于数组a说明为...
Oracle 数据库中的SQL是当今市场上功能最强大的SQL实现之一,而本书全面展示了这一工具的威力。如何才能让更多人有效地学习和掌握SQL呢?Karen Morton及其团队在本书中提供了专业的方案:先掌握语言特性,再学习...
1、 (1)索引是对数据库表中一列或多列进行排序的一种结构。 (2)Mysql中搜索引擎Innodb(聚簇索引)和Mysiam(非聚簇索引)都采用B+,oracle也采用B+树实现 注:聚簇索引:一张表只能建立一个聚簇索引,以主键建立...
select:从一个或多个表中检索一个或多个数据列。包含信息:想选择什么表,从什么地方选择。必须要有From子句。(最常用) 当从多张表里查询的时候,会产生笛卡尔积;可用条件过滤它。 当两个表有相同字段时必须加...
结构化查询语言(Structured Query Language)简称SQL,是一种关系数据库查询语言,用于存取数据以及查询、更新和管理关系数据库系统。 1.2 语句结构 1.2.1 数据查询语言(DQL) 对数据库进行的信息查询,select。 ...
另一种是"确认类paeser",它不但检测文档语法,结构树,而且比较解析你使用的元素标识是否遵守了相应DTD文件的规范。 Parser能独立使用,也可以成为编辑软件或浏览器的一部分。在后面的相关资源列表里,我列出了...
或者使用剪切功能将它复制到另一个地方。否则你可能看到回收站内的文件删除了这个又添加了那个。 Wsyscheck的或“dos删除功能”需要单独下载Wsyscheck的附加模块文件WDosDel.dat,将此文件与Wsyscheck放在一起会...
或者使用剪切功能将它复制到另一个地方。否则你可能看到回收站内的文件删除了这个又添加了那个。 Wsyscheck的或“dos删除功能”需要单独下载Wsyscheck的附加模块文件WDosDel.dat,将此文件与Wsyscheck放在一起会...
或者使用剪切功能将它复制到另一个地方。否则你可能看到回收站内的文件删除了这个又添加了那个。 Wsyscheck的或“dos删除功能”需要单独下载Wsyscheck的附加模块文件WDosDel.dat,将此文件与Wsyscheck放在一起会...
或者使用剪切功能将它复制到另一个地方。否则你可能看到回收站内的文件删除了这个又添加了那个。 Wsyscheck的或“dos删除功能”需要单独下载Wsyscheck的附加模块文件WDosDel.dat,将此文件与Wsyscheck放在一起会...
或者使用剪切功能将它复制到另一个地方。否则你可能看到回收站内的文件删除了这个又添加了那个。 Wsyscheck的或“dos删除功能”需要单独下载Wsyscheck的附加模块文件WDosDel.dat,将此文件与Wsyscheck放在一起会...
或者使用剪切功能将它复制到另一个地方。否则你可能看到回收站内的文件删除了这个又添加了那个。 Wsyscheck的或“dos删除功能”需要单独下载Wsyscheck的附加模块文件WDosDel.dat,将此文件与Wsyscheck放在一起会...
或者使用剪切功能将它复制到另一个地方。否则你可能看到回收站内的文件删除了这个又添加了那个。 Wsyscheck的或“dos删除功能”需要单独下载Wsyscheck的附加模块文件WDosDel.dat,将此文件与Wsyscheck放在一起会...
“重启删除”仅作为驱动无法加载情况下使用的一种辅助手段,“重启删除”与“Dos删除”可以同时使用。其列表都可以手动编辑,一行一个文件路径即可。关闭程序时如果上述两者之一存在删除列表,会问询是否执行。 ...
<br> “重启删除”仅作为驱动无法加载情况下使用的一种辅助手段,“重启删除”与“Dos删除”可以同时使用。其列表都可以手动编辑,一行一个文件路径即可。关闭程序时如果上述两者之一存在删除列表,会问询是否...
Javascript,简称为 JS,是一款能够运行在 JS解释器/引擎 中的脚本语言 JS解释器/引擎 是JS的运行环境: 1、独立安装的JS解释器 - NodeJS 2、嵌入在浏览器中的JS解释器 JS的发展史: 1、1992年 Nombas 开发...
if (n == 10) // 第一种判断方式 if (10 == n) // 第二种判断方式 如果少了个=号,编译时就会报错,减少了出错的可能行,可以检测出是否少了= ------------------------------------------------------------------...