关键词：排序的一般定义、排序的数学定义、排序的稳定性、多关键字排序、排序中的关键操作、排序的审判
0. 排序的一般定义
排序是计算机内经常进行的一种操作，其目的是将一组无序的数据元素调整为有序的数据元素。
1. 排序的数学定义
2. 排序的稳定性
如果在序列中有两个数据元素r[i]和r[j]，他们的关键字k[i] == k[j]，且在排序之前，对象r[i]在r[j]前面：
如果在排序之后，对象r[i]仍在对象r[j]的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。
3. 多关键字排序
排序时需要比较的关键字多于一个时：
- 排序结果首先按关键字1进行排序
- 当关键字1相同时按关键字2进行排序
... - 当关键字n-1相同时按关键字n进行排序
对于多关键字排序，只需要在比较操作时考虑多个关键字即可！
4. 排序中的关键操作
- 比较：任意两个数据元素通过比较操作确定先后次序
- 交换：数据元素之间交换才能得到预期结果
5. 排序的审判
- 时间性能：关键性能差异体现在比较和交换的数量
- 辅助存储空间：为完成排序操作需要的额外的存储空间，必要时可以空间换时间
- 算法的实现复杂性：过于复杂的排序法可能影响可读性和维护性
6. DTLib中排序类
排序类的继承关系图
7. 小结
- 排序时数据元素从无序到有序的过程
- 排序具有稳定性，是选择排序算法的因素之一
- 比较和交换是排序的基本操作
- 多关键字排序与单关键字排序无本质区别
- 排序的时间性能是区分排序算法好坏的主要因素
声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4
网友评论