当前课程知识点:C++语言程序设计进阶 > 第九章 模板与群体数据 > 排序 > 交换排序
两两比较待排序序列中的元素,并交换不满足顺序要求的各对元素,直到全部满足顺序要求为止。
起泡排序举例:对整数序列 8 5 2 4 3 按升序排序
首先将第一个元素与第二个元素进行比较,若为逆序,则将两元素交换。然后比较第二、第三个元素,依次类推,直到第n-1和第n个元素进行了比较和交换。此过程称为第一趟起泡排序。经过第一趟,最大的元素便被交换到第n个位置。
对前n-1个元素进行第二趟起泡排序,将其中最大元素交换到第n-1个位置。
如此继续,直到某一趟排序未发生任何交换时,排序完毕。对n个元素的序列,起泡排序最多需要进行n-1趟。
template <class T> void mySwap(T &x, T &y) { T temp = x; x = y; y = temp; } template <class T> void bubbleSort(T a[], int n) { int i = n – 1; while (i > 0) { int lastExchangeIndex = 0; for (int j = 0; j < i; j++) if (a[j + 1] < a[j]) { mySwap(a[j], a[j + 1]); lastExchangeIndex = j; } i = lastExchangeIndex; } }
大家好
欢迎回来继续C++语言程序设计
这一节我们来学习交换排序
我们来学习交换排序中
最简单的一种叫起泡排序
交换排序的基本思想呢
就是按照某种比较规则
两两比较这个序列中的元素
如果发现他们的次序关系
不符合我们最终的要求
那么就把它换一下
当然
不同的交换排序算法呢
会按不同的规则
来对数据元素进行比较
那最简单的一个办法呢
就是依次两两比较
相邻元素依次两两比较
这就是起泡排序
我们来看一下
这个起泡排序的图示
在这个示例中呢
我们用这样一组数据
8 5 2 4 3
来演示
这个起泡排序的这么一个过程
我们希望按照
由小到大的次序排列
也就是最后要形成
2 3 4 5 8
这样一个序列
那起泡排序它的思想是什么呢
就是相邻的数据元素两两比较
如果次序不合适就交换
那现在我们把这个数据序列
竖着写
好 我们就看到
首先8和5比较
这时候8和5需要交换
因为5比较小 8比较大
8要往小交换 5要往上升
然后8再跟2比较
2又上升 8又下降
8继续再跟4比较
4上升 8下降
8再跟3比较
3上升 8沉底
所以经过第一趟
这个结果我们看到
最大的元素8沉底了
而小的元素呢
都依次往上升了一个
好 接下来下一趟
还是做同样的比较
只不过这一次
已经沉底的这个8
就不用再参与比较了
5和2比较
2上升 5下降
5和4比较
4上升 5下降
5和3比较
3上升 5下降
经过第二趟5又沉底了
现在沉底两个元素了
继续还要进行
就是2跟4比较
那么2本来就小 4比较大
这一个没有发生交换
4跟3比较
3比较小 交换到上面去
4往下沉
这一趟又沉底了一个4
那么接下来再比较下一趟
2跟3比较
这一次没有发生交换
那么这个就是很形象的一个说法
起泡排序
小的数据像气泡一样往上升
那么最大的数据每次下沉
那这样的起泡排序的算法
大家想想看
如果你拿到的这个数据序列
一开始就有序
或者已经大部分有序了
你还要进行这么多趟吗
其实就不用了
起泡排序呢
如果有n个元素
那么最多进行n-1趟比较和交换
但是如果
这个序列本来就已经有序
或者大部分有序了
我们就没有必要完全得
走完这n-1趟比较和交换
因为
如果某一趟比较之后
没有发生任何交换的话
就说明整个数据序列已经有序了
这个时候就可以停止这个过程了
接下来呢
我们还是以函数模板的方式
来实现这个起泡排序的算法
这是
这个起泡排序的函数模板的代码
在起泡排序中呢
也大量要用到元素之间的交换
所以还是将交换
单独写为一个独立的函数模板
这个起泡排序思想就是
相邻的数据元素两两比较
次序不合适就交换
一轮一轮地走
每一轮一个最大的沉底
小的往上升
好 那怎么控制
还要不要进行下一轮的比较
和交换呢
这里用这个变量i来控制
i的初始值是n-1
然而一开始第一轮总是要做的
我们先进去看看什么时候
它就不用交换了
好 这里要保存一个
lastExchangeIndex
就是最后一次发生交换的
那个元素的下标要记下来
为什么要记它呢
一会就看到了
好
现在我们进到内层for循环中
两两比较进行交换
这个呢从0开始
到i-1为止
就是第i轮循环
不用把所有元素都交换掉
都比较一遍
因为最后面的元素
已经是最大的了
如果是由小到大排序的话
所以每一轮它就是下标控制
从0开始到i-1
这样两两比较
a j+1跟a j比较
如果大小标的数据更小的话
那么升序排列它就
如果要求升序排列
它就不满足要求了
如果要求降序排序
那你把这个变成大于号就行了
这个我们假设是要由小到大排序
好 次序不合适呢
就调用mySwap交换这两个元素
交换完了以后
要存下刚才最后交换的
这个元素的下标
当这内层for循环执行完了以后
将这个lastexchangeIndex
赋值给i
这是最后一次交换这个下标
然后呢
这个while循环就要看
如果i是大于0的
就说明刚才这一趟发生了交换
应该继续再做下一趟
如果它等于0了
那就不需要进行下一趟交换了
那么大家呢
也可以说我做一个简单的
外层循环控制它
一共走n-1轮
内层循环控制它两两比较
那样对于一些基本有序的
或者是完全有序的序列呢
就要做好多冤枉的比较
它又不需要交换 对吧
那么用这样的方式
去控制有些对于基本有序的
或者说刚排序了
走了两轮以后
已经就有序了
这样的序列呢
就不必继续去比较和交换了
而且这个i呢
记下了lastExchangeIndex
它还可以控制内层这个for循环
比较到哪个元素就为止
还可以控制这一点
当然我们也可以用另外一种方式
用true false
来记录有没有发生交换
那么那个记录呢
就不能控制内层循环
已执行到哪儿为止
这个大家可以仔细琢磨琢磨
然后可以把这里面的一些算法
按照你自己的想法
做一些不同的修改
看看它的效率呢
可能会有少许的差别
-导学
--导学
-继承的基本概念和语法
-第七章 继承与派生--继承的基本概念和语法习题
-继承方式
-第七章 继承与派生--继承方式
-基类与派生类类型转换
-第七章 继承与派生--基类与派生类类型转换
-派生类的构造和析构
--派生类的构造函数
--派生类的析构函数
--第七章 继承与派生--派生类的构造和析构
-派生类成员的标识与访问
--虚基类
-第七章 继承与派生--派生类成员的标识与访问
-小结
--小结
-综合实例
--第七章综合实例
-实验七
--实验七
-导学
--导学
-第八章 多态性--导学
-运算符重载
--运算符重载的规则
-第八章 多态性--运算符重载
-虚函数
--虚函数
--虚析构函数
--虚表与动态绑定
-第八章 多态性--虚函数
-抽象类
--抽象类
--第八章 多态性--抽象类
-override与final
-第八章 多态性--override与final
-小结
--第八章小结
-综合实例
--第八章综合实例
-实验八
--实验八
- 第八章讲义
-导学
--导学
-模板
--函数模板
--类模板
-第九章 模板与群体数据--模板
-线性群体
--线性群体的概念
-第九章 模板与群体数据--线性群体
-数组
--数组类模板
-链表
--链表类模板
-第九章 模板与群体数据--链表
-栈
--栈类模板
--栈类模板课后习题
--例9-9 栈的应用课后习题
-队列
--队列类模板
-第九章 模板与群体数据--队列
-排序
--排序概述
--插入排序
--选择排序
--交换排序
-第九章 模板与群体数据--排序
-查找
--查找
--查找课后习题
-小结
--小结
-综合实例
--综合实例
-实验九
--实验九
- 第九章讲义
-导学
--导学
-泛型程序设计及STL的结构
--STL简介
-第十章 泛型程序设计与C++标准模板库--泛型程序设计及STL的结构
-迭代器
--迭代器
-第十章 泛型程序设计与C++标准模板库--迭代器
-容器的基本功能与分类
-第十章 泛型程序设计与C++标准模板库--容器的基本功能与分类
-顺序容器
--顺序容器的特征
--第十章 泛型程序设计与C++标准模板库--顺序容器
-关联容器
--集合
--映射
-第十章 泛型程序设计与C++标准模板库--关联容器
-函数对象
--函数对象
--函数适配器
-算法
--算法
-小结
--第十章小结
-综合实例
--综合实例
-实验十
--实验十
- 第十章讲义
-导学
--导学
-I/O流的概念及流类库结构
-第十一章 流类库与输入/输出--I/O流的概念及流类库结构
-输出流
--输出流概述
--向文本文件输出
--向二进制文件输出
--向字符串输出
-第十一章 流类库与输入/输出--输出流
-输入流
--输入流概述
--输入流应用举例
--从字符串输入
-第十一章 流类库与输入/输出--输入流
-输入/输出流
--输入/输出流
-第十一章 流类库与输入/输出--输入/输出流
-小结
--小结
-综合实例
--综合实例
-实验十一
--实验十一
- 第十一章讲义
-导学
--第12章导学
-异常处理的思想与程序实现
-第十二章 异常处理--异常处理的思想与程序实现
-异常处理中的构造与析构
-第十二章 异常处理--异常处理中的构造与析构
-标准程序库异常处理
-第十二章 异常处理--标准程序库异常处理
-小结
--第12章小结
-综合实例
--综合实例
-实验十二
--实验十二
- 第十二章讲义