排序的一般定义：

• 排序是计算机内经常进行的一种操作，其目的是将一组“无序”的数据元素调整为“有序”的数据元素；
• 无序到有序就是排序；

排序的数学定义：

       假设含 n 个数据元素序列为{R1, R2, ..., Rn}， 其相应的关键字序列为 {K1, K2, ..., Kn}，这些关键字相互之间可以进行比较，即：在它们之间存在着这样一个关系  Kp1 <= Kp2 <= ... <= Kpn，  按此固有关系将上式记录序列重新排列为  {Rp1, Rp2, ..., Rpn}的操作称为排序。

排序的稳定性：

       如果在序列中有两个数据元素 r[i] 和 r[j]，它们的关键字 k[i] == k[j]，且在排序之前，对象 r[i] 排在 r[j] 前面；如果在排序之后，对象 r[i] 仍在对象 r[j] 的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的；

             
排序中的关键操作：

       比较：任意两个数据元素通过比较操作确定先后次序；

       交换：数据元素之间需要交换才能得到预期效果（无序变有序）；

排序算法的选择：

       时间性能：关键性能差异体现在比较和交换的数量；

       辅助存储空间：为完成排序操作需要的额外的存储空间：嵌入式开发，空间资源受限；必要时可以“空间换时间”；

       算法的实现复杂性：过于复杂的排序法可能影响可读性和可维护性；

小结：

• 排序是数据元素从无序到有序的过程；
• 排序具有稳定性，是选择排序算法的（主要）因素之一；
• 比较和交换是排序的基本操作；
• 排序的时间性能是区分排序算法好坏的主要因素；

掌握本节内容