当前课程知识点：C++语言程序设计进阶 > 第九章 模板与群体数据 > 排序 > 排序概述
排序是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。
数据元素: 数据的基本单位。在计算机中通常作为一个整体进行考虑。一个数据元素可由若干数据项组成。
关键字: 数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。
在排序过程中需要完成的两种基本操作
比较两个数的大小
调整元素在序列中的位置
内部排序：待排序的数据元素存放在计算机内存中进行的排序过程。
外部排序：待排序的数据元素数量很大，以致内存存中一次不能容纳全部数据，在排序过程中尚需对外存进行访问的排序过程。
插入排序
选择排序
交换排序
大家好
欢迎回来继续学习
C++语言程序设计
现在我们开始学习排序
首先呢
我们来了解一下
排序的一些基本的概念
排序是做什么呢
就是把一个原本
可能是无序的序列
或者说数据任意排列的序列
把它变成一个
有序排列的序列
升序也好 降序也好
这个过程 叫做排序
在排序的算法中呢
我们会涉及到这样几个概念
第一个是数据元素
比如说
我们回忆一下
以前用过的一维数组
那它每一个数组元素
其实就是我们这里面说的
一个数据元素
它是数据的基本单位
在排序的过程中呢
我们会将一个数据元素
作为一个整体进行考虑
其实一个数据元素
当然也可以由若干数组项组成
比如说我们的对象数组
那每一个对象里面
就存放着一组数据
它有好多个数据成员
实际上
就是我们这里面说的数据项
一个元素可以是
若干数据项构成的
但是它叫做一个元素
就是排序的时候在交换
在比较 在移动的时候
都把它作为一个整体
另一个概念就是关键字
我们说要将一组数据
按照某种次序去排列
那如果是简单整数
那倒没有关系
1 2 3 4 5往上排就行了
如果我们要对一组对象
比如说对一组学生信息进行排序
那就牵扯到
到底你是你按学号排序
还是按姓名排序
或者是按成绩排序呢
所以这个时候我们就要指定
这一次排序
我们关键字是什么
关键字是数据元素中
某个数据项的值
用它可以标识
或者识别一个数据元素
用来唯一标识
一个数据元素的关键字呢
叫做主关键字
主关键字一般来讲
是不允许重复的
那么其他的关键字呢
可以用它来排序
作为一个因素
但是它可以重复
比如说
还是以学生信息为例
一般来讲
学号是不允许重复的
但是我们也可以按照姓名
这个关键字排序
那姓名呢
就是有可能重复的
在排序过程中
我们需要完成两种基本操作
一个是比较大小
一个是调整位置
排序又分成内部排序
和外部排序
内部排序呢
就是把全部待排序的数据
都放在内存里面
我们在内存里面操作
这整个排序过程
有的时候呢
需要排序的数据规模太大
全部装到内存里就装不下了
这个时候
就需要按照我们的算法要求
分批把要排序的数据导入内存
要有一些内外存的交换
那么这个就涉及到了
外排序的算法
在这门课里面呢
我们只以简单的几个
内排序算法为例
给大家介绍一点
排序的基本概念
和简单的程序
外排序呢
就不在
我们这门课的课程范围之内了
我们要介绍的
几类简单的排序算法呢
包括插入排序 选择排序
和交换排序
我们会在这每一类排序算法中
选择一个最简单
最容易编程实现的算法
作为例题
但是呢
最简单的算法
它往往不是效率最高的算法
大家要了解更多
效率更高的算法呢
欢迎大家去学习数据结构课
-导学
--导学
-继承的基本概念和语法
-第七章 继承与派生--继承的基本概念和语法习题
-继承方式
-第七章 继承与派生--继承方式
-基类与派生类类型转换
-第七章 继承与派生--基类与派生类类型转换
-派生类的构造和析构
--派生类的构造函数
--派生类的析构函数
--第七章 继承与派生--派生类的构造和析构
-派生类成员的标识与访问
--虚基类
-第七章 继承与派生--派生类成员的标识与访问
-小结
--小结
-综合实例
--第七章综合实例
-实验七
--实验七
-导学
--导学
-第八章 多态性--导学
-运算符重载
--运算符重载的规则
-第八章 多态性--运算符重载
-虚函数
--虚函数
--虚析构函数
--虚表与动态绑定
-第八章 多态性--虚函数
-抽象类
--抽象类
--第八章 多态性--抽象类
-override与final
-第八章 多态性--override与final
-小结
--第八章小结
-综合实例
--第八章综合实例
-实验八
--实验八
- 第八章讲义
-导学
--导学
-模板
--函数模板
--类模板
-第九章 模板与群体数据--模板
-线性群体
--线性群体的概念
-第九章 模板与群体数据--线性群体
-数组
--数组类模板
-链表
--链表类模板
-第九章 模板与群体数据--链表
-栈
--栈类模板
--栈类模板课后习题
--例9-9 栈的应用课后习题
-队列
--队列类模板
-第九章 模板与群体数据--队列
-排序
--排序概述
--插入排序
--选择排序
--交换排序
-第九章 模板与群体数据--排序
-查找
--查找
--查找课后习题
-小结
--小结
-综合实例
--综合实例
-实验九
--实验九
- 第九章讲义
-导学
--导学
-泛型程序设计及STL的结构
--STL简介
-第十章 泛型程序设计与C++标准模板库--泛型程序设计及STL的结构
-迭代器
--迭代器
-第十章 泛型程序设计与C++标准模板库--迭代器
-容器的基本功能与分类
-第十章 泛型程序设计与C++标准模板库--容器的基本功能与分类
-顺序容器
--顺序容器的特征
--第十章 泛型程序设计与C++标准模板库--顺序容器
-关联容器
--集合
--映射
-第十章 泛型程序设计与C++标准模板库--关联容器
-函数对象
--函数对象
--函数适配器
-算法
--算法
-小结
--第十章小结
-综合实例
--综合实例
-实验十
--实验十
- 第十章讲义
-导学
--导学
-I/O流的概念及流类库结构
-第十一章 流类库与输入/输出--I/O流的概念及流类库结构
-输出流
--输出流概述
--向文本文件输出
--向二进制文件输出
--向字符串输出
-第十一章 流类库与输入/输出--输出流
-输入流
--输入流概述
--输入流应用举例
--从字符串输入
-第十一章 流类库与输入/输出--输入流
-输入/输出流
--输入/输出流
-第十一章 流类库与输入/输出--输入/输出流
-小结
--小结
-综合实例
--综合实例
-实验十一
--实验十一
- 第十一章讲义
-导学
--第12章导学
-异常处理的思想与程序实现
-第十二章 异常处理--异常处理的思想与程序实现
-异常处理中的构造与析构
-第十二章 异常处理--异常处理中的构造与析构
-标准程序库异常处理
-第十二章 异常处理--标准程序库异常处理
-小结
--第12章小结
-综合实例
--综合实例
-实验十二
--实验十二
- 第十二章讲义
