当前课程知识点：数据结构 > 第8章 排序 > 8.1 概念 > 讲解
同学们好，本章
我们来学习排序，这一章分为以下五部分内容
我们先来看第一部分，概述，第一个概念，排序
排序应该说是我们平时编写很多程序，都涉及到的一类操作
我们对若干数据元素，按关键字以非递减或非递增的顺序进行排列的操作，就叫排序
因为关键字可能相同
也就是说
我们给出来的关键字，不是主关键字
而是次关键字
这时候，我们就不能说递增
而是非递减
如果我们按照关键字非递减的顺序排列
这时候，我们就说排成正序
反之
按照关键字非递增的顺序排列
这时候，就叫排成逆序
没有做特别说明的情况下
我们都是将给定的若干关键字排成正序
通常，将元素的比较和移动操作，视为算法的基本步骤
我们后面，会讲很多的排序算法
在这些排序算法的循环当中，主要涉及到两类操作
一类是if语句
它的条件是，判断两个元素的大小关系
这个是比较，还有一类语句
是赋值语句
也就是进行元素的移动
所以，我们在看排序算法的时间复杂度的时候
通常是以比较和移动操作，来作为算法的基本步骤
现在来看
第二个概念，排序算法的稳定性
我们以排序算法A，对给定的任意元素序列，进行排序
注意，是任意的元素序列
如果关键字相同的那些元素
它们的先后关系，在排序前后总一致，注意，是总一致，则说
A是稳定的
否则
只要先后顺序发生了变化
我们就说，A是不稳定的
比如，我们给出2、3、2、1这四个关键字
由于有两个2，我用颜色来区分这两个2，它们经过某一个排序算法A
排完序之后
当然是1、2、2、3，排成正序
这两个2，大家发现，在排序前后
它们的先后位置发生了变化
那我可以马上说，你所采用的排序算法A，是不稳定的
因为，关键字相同的元素
它们的先后位置，发生了变化
我们再看另外一种情况
同样的2、3、2、1，还是采用排序算法A进行排序
得到的两个2，它们的先后关系没有发生变化
这时候，是否能说A是稳定的呢
实际上，是不行的
因为，根据我们前面的定义
如果你的算法对任意的元素序列，都会让那些关键字相同的元素
它们的先后关系，在排序前后总一致
这时候，你才能说A是稳定的
现在，仅仅给出某一个具体的序列
尽管它们的先后关系没有发生变化
这时候，也不能说你采用的排序算法是稳定的
但是，我们又不太可能穷举出
所有的序列
所以，我们分析排序算法的稳定性，并不是通过具体的序列来分析的
而是通过分析算法当中的步骤来确定的
第三个，排序算法的分类
我们可以按照元素的存放位置，来进行分类
也可以按照排序所采用的策略，来进行分类
我们先按位置来分
如果要排序的全部元素，都已经放在内存当中了
这时候，我们采用的排序算法
就是内部排序
我们这门课当中所讲的排序算法，都是内部排序
所有要排的元素，都已经事先放在内存当中了
如果你要排序的关键字个数
非常的大
它的量级
可能超过了计算机内存的量级
这时候，很明显，就不能用内部排序了
那涉及到一类排序，叫外部排序
外部排序，部分待排数据是存放在外存当中的
在排序过程当中
要涉及到内外存的数据交换
比如，我们现在流行的大数据
它所采用的排序算法，很明显
我们这门课讲的内部排序，就不适合了
如果我们按照排序策略来分
可以分为以下几类
第一类，插入排序
它基于的思想是，将元素插入到有序表
具体来说
我们会介绍直接插入排序和希尔排序
第二类排序
是基于交换的思想
我们称为交换排序
它是在排序过程当中，交换两个位置的元素
具体来说
有冒泡排序、快速排序，第三类排序
叫选择排序
它每次找出当前序列当中的最大者或者最小者
找到了之后，把这个最大者或最小者放到合适的位置
后面再去找次大者或次小者
具体来说
我们会介绍简单选择排序和堆排序
第四类排序
叫归并排序
它的思想是，合并已经有序的多个子表
最终形成一个有序的表
我们这一章，主要介绍这四类排序
还有一类排序，叫基数排序
它所采用的思想，跟我们前面介绍的这四类
不太一样
它是基于分配的思想
又叫做桶排序
在本章当中
我们不关注这类排序
现在，我们来看待排元素的存储
为了方便后面描述算法
我们这里约定，以顺序(方式)存储待排元素
实际上
你以链式存储
也可以
既然是顺序存储
我们得定义一个容量
MAX_SIZE
然后
我们给关键字类型起一个别名
这里，我们约定关键字类型就是int型
接着
我们定义待排元素的类型
我们只关心元素的关键字
因为，对于排序来说
我们不关心
除了关键字之外的其他的成员
别名ElemType，在前面已经见过很多了
第二个结构体，第一个成员是一个数组
类型就是我们之前定义的元素类型
这个数组的长度是MAX_SIZE+1
既然加了一个1
说明，我们约定0下标不用，第i个元素
就存放在下标i的位置
我们这里之所以把它定义成一个数组名
之前，我们在定义静态查找表的时候
我们定义成了一个指针，指针和数组名，其实本质上是差不多的
因为，对于排序算法
我们不可能去做插入和删除
所以，定义成数组名就可以了
既然是顺序存储
除了这个容量之外
我们还得有一个长度
标识你的数组当中，有多少个待排的元素
这个成员是length
然后
起一个别名，SqList(顺序表)
这跟我们第一章当中讲的顺序表，是一样的
用它作为所有待排元素的类型
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
