当前课程知识点:C++语言程序设计进阶 > 第九章 模板与群体数据 > 排序 > 插入排序
每一步将一个待排序元素按其关键字值的大小插入到已排序序列的适当位置上,直到待排序元素插入完为止。
template <class T> void insertionSort(T a[], int n) { int i, j; T temp; for (int i = 1; i < n; i++) { int j = i; T temp = a[i]; while (j > 0 && temp < a[j - 1]) { a[j] = a[j - 1]; j--; } a[j] = temp; } }
大家好
欢迎继续回来学习
C++语言程序设计
接下来我们来学习
插入排序
我们来学习插入排序里面
最简单的一种排序
就是直接插入排序
它的算法的基本思想就是
从待排序序列
也就是无序的这个数据系列中
每一次依次拿出一个元素来
插入到
已排序序列里面的合适的位置
使得插入这个数据以后
已排序序列
仍然维持它的原来有序
一个一个地从未排序序列中
拿出元素来插入到
已排序序列的合适位置
直到未排序序列的元素
全部拿完了
那么整个序列
就完全变成有序的了
现在我们来看
这个插入排序的示意图
假设初始状态
我们有这样一组数据
5 4 10 20 12 3
它是无序的
现在我们要按照由小到大的次序
来排列这一组数据
也就是说要对它进行排序
这里呢
我们用直接插入排序的办法
那这个算法呢
它首先假设
第一个数据5
就是已排序序列的初始状态
它就一个数
认为它是有序的
当然也没什么问题
那接下来的任务
就是将从4开始到3
这剩下的
存在于无序的
未排序序列中的数据
一个个依次取出来
插入到合适的位置去
第一次我们先取出4来
4应该往哪儿插呢
我们从已排序序列的最末尾
开始比较
现在就一个数
拿4跟5比较一下
4比5要小
所以把它插入到5的前面
当我们把4拿出来的时候
看这个位置已经空出来了
所以5可以挪到后面
4插进去
接下来呢
就是拿出10
10跟已排序序列
最末尾的元素比较
它比5要大
所以它插入在5后面
10就落在当前的位置了
同样拿20来
要往里面插入
比较的结果也是
20就落在当前位置了
再下面一个元素是12
12跟20比较
12要比20小
所以无论将来12插入到哪儿
20都要往后移一个位置
所以20先后移
然后12再跟前一个元素比较
跟10比较
12比10大
所以呢
12就应该落在当前
空出来的这个位置
12就插入进去了
最后呢 还剩一个3
3拿出来以后跟20比较
20要往后移
跟12比较 12也要往后移
一个一个比较
它们都比3要大
所以的现在的元素都后移了
再往前走没有了
整个序列到头了
这个时候呢
就意味着3
在当前的位置落下
它放在最头上了
这样呢
一个未排序序列到此为止
就全部变成已排序的有序序列了
接下来呢
我们就来看
用程序怎么样实现
这个直接插入排序的过程
这里呢
我们不是写了一个普通的函数
而是写了一个函数模板
也就是说
它可以适用于
多种不同类型数据排序
当然了
这个排序算法中我们要看
它都有哪些运算
如果我们想用这个函数模板
去对不同类型的数据
进行排序的话
必须这个类型能够进行
函数体里面规定的这些运算
才可以
在这个直接插入排序函数模板中
我们看
这个它的函数模板的参数
是T类型的
也就是说
它可以
对任何任意类型的数据序列
进行排序
但是是不是
真的任意类型的数据序列
都可以用这个进行排序呢
那我们排序中还用到了
比如说赋值运算
用到了比较关系运算
这些运算是不是可以用在
你指定的类型上
这个我们使用的时候要注意
如果是对基本类型的数据
进行排序
没有问题
如果是对类的对象进行排序
那么这个类应该重载过
赋值运算符
应该重载过关系运算符
这样才可以
好 那看这个函数的数据参数呢
有一个数组
还有呢
数组元素个数
现在看
主要的排序
在这个for循环中进行
那么插入排序
就是假设首元素
也就是a0
是已排序序列的初始状态
那需要插入的元素呢
就是从下标为1的元素开始
一个个往里面插入
首先呢
可以这个循环就从1开始
到最后一个元素
第n-1个元素
那这里呢
我们需要把要插入的这个数据ai
从它的空间中取出来
复制到一个临时空间temp里面然后接下来
我们要用一个while循环
做什么事情呢
移动数据
这个循环里面用到了
j来控制下标
那j的初始状态就是i
那看每一轮循环做了什么
将a j-1里面的数据
移动到aj里面去
什么情况下这样移动呢
首先j大于0
这是还没有到头
从后往前比较 还没有到头
然后这个temp要小于a j-1
也就是这种情况下
a j-1才需要往后移
只要这种情况满足
就继续循环
每一个循环完了以后j-1
什么时候发现这个temp
不小于a j-1了
或者j达到0了
就说明当前位置
就是应该插入temp里面
数据的位置了
所以就将temp里面的数据
放在当前位置就可以了
这个程序非常简单
-导学
--导学
-继承的基本概念和语法
-第七章 继承与派生--继承的基本概念和语法习题
-继承方式
-第七章 继承与派生--继承方式
-基类与派生类类型转换
-第七章 继承与派生--基类与派生类类型转换
-派生类的构造和析构
--派生类的构造函数
--派生类的析构函数
--第七章 继承与派生--派生类的构造和析构
-派生类成员的标识与访问
--虚基类
-第七章 继承与派生--派生类成员的标识与访问
-小结
--小结
-综合实例
--第七章综合实例
-实验七
--实验七
-导学
--导学
-第八章 多态性--导学
-运算符重载
--运算符重载的规则
-第八章 多态性--运算符重载
-虚函数
--虚函数
--虚析构函数
--虚表与动态绑定
-第八章 多态性--虚函数
-抽象类
--抽象类
--第八章 多态性--抽象类
-override与final
-第八章 多态性--override与final
-小结
--第八章小结
-综合实例
--第八章综合实例
-实验八
--实验八
- 第八章讲义
-导学
--导学
-模板
--函数模板
--类模板
-第九章 模板与群体数据--模板
-线性群体
--线性群体的概念
-第九章 模板与群体数据--线性群体
-数组
--数组类模板
-链表
--链表类模板
-第九章 模板与群体数据--链表
-栈
--栈类模板
--栈类模板课后习题
--例9-9 栈的应用课后习题
-队列
--队列类模板
-第九章 模板与群体数据--队列
-排序
--排序概述
--插入排序
--选择排序
--交换排序
-第九章 模板与群体数据--排序
-查找
--查找
--查找课后习题
-小结
--小结
-综合实例
--综合实例
-实验九
--实验九
- 第九章讲义
-导学
--导学
-泛型程序设计及STL的结构
--STL简介
-第十章 泛型程序设计与C++标准模板库--泛型程序设计及STL的结构
-迭代器
--迭代器
-第十章 泛型程序设计与C++标准模板库--迭代器
-容器的基本功能与分类
-第十章 泛型程序设计与C++标准模板库--容器的基本功能与分类
-顺序容器
--顺序容器的特征
--第十章 泛型程序设计与C++标准模板库--顺序容器
-关联容器
--集合
--映射
-第十章 泛型程序设计与C++标准模板库--关联容器
-函数对象
--函数对象
--函数适配器
-算法
--算法
-小结
--第十章小结
-综合实例
--综合实例
-实验十
--实验十
- 第十章讲义
-导学
--导学
-I/O流的概念及流类库结构
-第十一章 流类库与输入/输出--I/O流的概念及流类库结构
-输出流
--输出流概述
--向文本文件输出
--向二进制文件输出
--向字符串输出
-第十一章 流类库与输入/输出--输出流
-输入流
--输入流概述
--输入流应用举例
--从字符串输入
-第十一章 流类库与输入/输出--输入流
-输入/输出流
--输入/输出流
-第十一章 流类库与输入/输出--输入/输出流
-小结
--小结
-综合实例
--综合实例
-实验十一
--实验十一
- 第十一章讲义
-导学
--第12章导学
-异常处理的思想与程序实现
-第十二章 异常处理--异常处理的思想与程序实现
-异常处理中的构造与析构
-第十二章 异常处理--异常处理中的构造与析构
-标准程序库异常处理
-第十二章 异常处理--标准程序库异常处理
-小结
--第12章小结
-综合实例
--综合实例
-实验十二
--实验十二
- 第十二章讲义