46_排序的基本概念

关键词：排序的一般定义、排序的数学定义、排序的稳定性、多关键字排序、排序中的关键操作、排序的审判

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