排序的基本概念
标签: 数据结构
学习人数: 21.2k

排序的一般定义:

      

排序的数学定义:

       假设含 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] 的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的;

             
排序中的关键操作:

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

       交换:数据元素之间需要交换才能得到预期效果(无序变有序);

             

排序算法的选择:

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

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

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


小结:

登录查看完整内容


课后作业

掌握本节内容


登录后开始许愿

暂无评论,来抢沙发