当前课程知识点:C++语言程序设计进阶 > 第九章 模板与群体数据 > 排序 > 选择排序
每次从待排序序列中选择一个关键字最小的元素,(当需要按关键字升序排列时),顺序排在已排序序列的最后,直至全部排完。
template <class T> void mySwap(T &x, T &y) { T temp = x; x = y; y = temp; } template <class T> void selectionSort(T a[], int n) { for (int i = 0; i < n - 1; i++) { int leastIndex = i; for (int j = i + 1; j < n; j++) if (a[j] < a[leastIndex]) leastIndex = j; mySwap(a[i], a[leastIndex]); } }
大家好
欢迎回来继续学习
C++语言程序设计
这一节我们来学习
选择排序
我们来看一个
选择排序里面的
最简单的一种方式
就是简单选择排序
这个算法的思想呢
就是从这个未排序序列中
每一次按照关键字的值
去选出一个数据来
放到已排序序列的末尾
那么选最大的
还是选最小的呢
取决于你要升序排列
还是降序排列
如果我们是希望
由小到大排列的话
那么每一次
就从这个待排序的序列中
经过比较
选出一个最小的元素
依次排在已排序序列的末尾
每次选一个
每次选一个
直到未排序系列里面的全部元素
都被选出来了
那么整个序列也就有序了
现在我们来看一下这个示意图
现在我们来看
还是以这个序列为例
5 4 10 20 12 3
那么这个简单选择排序的算法
它关键在于选择
每次要从这个未排序序列中
选出一个最小的元素来
依次排列在
已排序序列的最末尾的位置去
追加到已排序序列的最末尾
那么第一轮呢
显然我们应该选出这个3
怎么能选出这个最小的3呢
简单选择排序
用的是从头到尾比较一遍的办法
把这个序列的数据
一个一个进行比较
那比较一轮
肯定又找出那个最小的来了
那就把3取出来
那么这个时候怎么能把3
排到前面去呢
不用移动大量的数据
3和最前面的5进行交换就行了
这样3就放到了
已排序序列的末尾
那下一轮呢
就选出了4
那这个时候看到
4已经是在最头上的位置了
那就4
依然落在当前位置就可以了
接下来会选出这个5
5呢
我们需要把它排在4之后
也就是现在这个元素10
所在的位置
那这时候就把10拿出来
跟5交换一下
5就排到前面去了
那么接下来呢
再选出来的应该是10 12 20
依此类推
全部的元素都选完了呢
当然整个序列也就变成有序了
好 下面这个例题呢
就是一个
实现简单选择排序的函数模板
我们来看
这个程序上是怎么实现的
在选择排序中呢
我们经常需要用到一个
交换的功能
所以在这儿呢
我们单独写了一个mySwap
这个交换函数
用来交换两个参数x y
那接下来我们来看
这个函数模板里面
它也是排序
接受一个待排序的数组a
以及元素个数
选择了一个排序呢
是每一次从待排序序列中
选出一个最小的
放在已排序序列的末尾
也就是说待排序序列的头
因为它不用额外的空间
只用原来的数组
原地交换这样排序 对吧
那我们循环呢就是从0开始
到什么
到小于n-1
不用到最后一个
前面n-1个元素都确定了
最后一个元素
当然它就应该在最后了
那现在我们要用内层for循环
来选出当前的待排序序列中
最小的那个元素
首先我们就把最小元素的下标
初始化为i
就是开头这个位置
然后在这个循环中
每一次比较
一个一个元素依次比较
从第i+1个开始
到第n-1个
就是每次这样比较
发现更小的
就记下这个更小的元素
它的下标
这样内层for循环结束以后
这个listIndex里面放的
就是那个最小元素下标了
拿它跟ai进行交换就可以了
那这就是一个
简单选择排序的函数模板
-导学
--导学
-继承的基本概念和语法
-第七章 继承与派生--继承的基本概念和语法习题
-继承方式
-第七章 继承与派生--继承方式
-基类与派生类类型转换
-第七章 继承与派生--基类与派生类类型转换
-派生类的构造和析构
--派生类的构造函数
--派生类的析构函数
--第七章 继承与派生--派生类的构造和析构
-派生类成员的标识与访问
--虚基类
-第七章 继承与派生--派生类成员的标识与访问
-小结
--小结
-综合实例
--第七章综合实例
-实验七
--实验七
-导学
--导学
-第八章 多态性--导学
-运算符重载
--运算符重载的规则
-第八章 多态性--运算符重载
-虚函数
--虚函数
--虚析构函数
--虚表与动态绑定
-第八章 多态性--虚函数
-抽象类
--抽象类
--第八章 多态性--抽象类
-override与final
-第八章 多态性--override与final
-小结
--第八章小结
-综合实例
--第八章综合实例
-实验八
--实验八
- 第八章讲义
-导学
--导学
-模板
--函数模板
--类模板
-第九章 模板与群体数据--模板
-线性群体
--线性群体的概念
-第九章 模板与群体数据--线性群体
-数组
--数组类模板
-链表
--链表类模板
-第九章 模板与群体数据--链表
-栈
--栈类模板
--栈类模板课后习题
--例9-9 栈的应用课后习题
-队列
--队列类模板
-第九章 模板与群体数据--队列
-排序
--排序概述
--插入排序
--选择排序
--交换排序
-第九章 模板与群体数据--排序
-查找
--查找
--查找课后习题
-小结
--小结
-综合实例
--综合实例
-实验九
--实验九
- 第九章讲义
-导学
--导学
-泛型程序设计及STL的结构
--STL简介
-第十章 泛型程序设计与C++标准模板库--泛型程序设计及STL的结构
-迭代器
--迭代器
-第十章 泛型程序设计与C++标准模板库--迭代器
-容器的基本功能与分类
-第十章 泛型程序设计与C++标准模板库--容器的基本功能与分类
-顺序容器
--顺序容器的特征
--第十章 泛型程序设计与C++标准模板库--顺序容器
-关联容器
--集合
--映射
-第十章 泛型程序设计与C++标准模板库--关联容器
-函数对象
--函数对象
--函数适配器
-算法
--算法
-小结
--第十章小结
-综合实例
--综合实例
-实验十
--实验十
- 第十章讲义
-导学
--导学
-I/O流的概念及流类库结构
-第十一章 流类库与输入/输出--I/O流的概念及流类库结构
-输出流
--输出流概述
--向文本文件输出
--向二进制文件输出
--向字符串输出
-第十一章 流类库与输入/输出--输出流
-输入流
--输入流概述
--输入流应用举例
--从字符串输入
-第十一章 流类库与输入/输出--输入流
-输入/输出流
--输入/输出流
-第十一章 流类库与输入/输出--输入/输出流
-小结
--小结
-综合实例
--综合实例
-实验十一
--实验十一
- 第十一章讲义
-导学
--第12章导学
-异常处理的思想与程序实现
-第十二章 异常处理--异常处理的思想与程序实现
-异常处理中的构造与析构
-第十二章 异常处理--异常处理中的构造与析构
-标准程序库异常处理
-第十二章 异常处理--标准程序库异常处理
-小结
--第12章小结
-综合实例
--综合实例
-实验十二
--实验十二
- 第十二章讲义