什么是排序? 排序 口将序列中的记录按照排序码顺序排列起来 口排序码域的值具有不减(或不增)的顺序 内排序 口整个排序过程在内存中完成 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 什么是排序？ ◼ 排序 ❑ 将序列中的记录按照排序码顺序排列起来 ❑ 排序码域的值具有不减(或不增)的顺序 ◼ 内排序 ❑ 整个排序过程在内存中完成
排序问题 给定一个序列R={r1,r2,…,rn 口其排序码分别为k={k1,k2,…,kn 排序的目的:将记录按排序码重排 口形成新的有序序列R={r1,r2,…,rn} 口相应排序码为k={k1,k32,…k3n 排序码的顺序 口其中k21≤k2≤…≤kn,称为不减序 口或k1≥k2≥…≥k’n,称为不增序 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 排序问题 ◼ 给定一个序列R ={r1, r2, …，rn} ❑ 其排序码分别为k ={k1, k2, …，kn} ◼ 排序的目的：将记录按排序码重排 ❑ 形成新的有序序列R'= {r'1,r'2,…,r'n} ❑ 相应排序码为k'={k'1,k'2,…k'n} ◼ 排序码的顺序 ❑ 其中k'1≤k'2≤…≤k'n，称为不减序 ❑ 或k'1≥k'2≥…≥k'n ，称为不增序
正序vs.逆序 “正序”序列: 待排序序列正好符合排序要求 “逆序”序列: 把待排序序列逆转过来,正好符合排 序要求 例如,要求不升序列逆序! a96341208 正序! “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 正序 vs. 逆序 ◼ “正序”序列 ： 待排序序列正好符合排序要求 ◼ “逆序”序列 ： 把待排序序列逆转过来，正好符合排 序要求 ◼ 例如，要求不升序列 ❑ 08 12 34 96 ❑ 96 34 12 08 逆序！ 正序！
排序的稳定性 稳定性 口存在多个具有相同排序码的记录 排序后这些记录的相对次序保持不变 稳定性例1 口3412340896 稳定! a08123434′96 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 排序的稳定性 ◼ 稳定性 ❑ 存在多个具有相同排序码的记录 ❑ 排序后这些记录的相对次序保持不变 ◼ 稳定性例1 ❑ 34 12 34’ 08 96 ❑ 08 12 34 34’ 96 稳定！
排序的稳定性 稳定性 存在多个具有相同排序码的记录 排序后这些记录的相对次序保持不变 稳定性例2 口3412340896 a0812343496 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 排序的稳定性 ◼ 稳定性 ❑ 存在多个具有相同排序码的记录 ❑ 排序后这些记录的相对次序保持不变 ◼ 稳定性例2 ❑ 34 12 34’ 08 96 ❑ 08 12 34’ 34 96 不稳定！