7.1.1基本概念 什么是排序? 记录( Record):结点,进行排序的基 本单位 排序 关键码Key):唯一确定记录的一个 将序列中的记录按照排序码顺序排列起来 或多个域 排序码域的值具有不减(或不增)的顺序 排序码( Sort Key):作为排序运算依 内排序 的一个或多个 n整个排序过程在内存中完成 序列( equence):线性表 由记录组成 北大▲单张铭搞写 有,郭位詹命究 北大息_张铭写 排序问题 正序vs逆序 给定一个序列R={r1,r2,…,rn} “正序序列:待排序序列正好符合 其排序码分别为k={k1 排序要求 排序的目的:将记录按排序码重排 “逆序序列:把待排序序列逆转过 形成新的有序序列R'={rlpr2 n 来,正好符合排序要求 相应排序码为k={k'1,k2…,k23 ■排序码的顺序 例如,要求不升序列逆序 其中k1≤k2≤…≤kn,称为不减序 n08123496 或k'1≥k2,≥ka,称为不增序 °6341208-正序! 北大影_歌张写 权质有轨国邮究 真大影张帖写 叔新有,量究 排序的稳定性 排序算法的衡量标准 稳定性 时间代价:记录的比较和移动次数 存在多个具有相同排序码的记录 ■空间代价 排序后这些记录的相对次序保持不变 ■例如,341234′0896 0812343496—稳定 算法本身的繁杂程度 081234′3496—不稳定 北真大学张铭编写 聊张帖写 权新有,究2 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 7 7.1.1 基本概念 „ 记录(Record)：结点，进行排序的基 本单位 „ 关键码(Key)：唯一确定记录的一个 或多个域 „ 排序码(Sort Key)：作为排序运算依 据的一个或多个域 „ 序列(Sequence)：线性表 „ 由记录组成 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 8 什么是排序？ „ 排序 „ 将序列中的记录按照排序码顺序排列起来 „ 排序码域的值具有不减(或不增)的顺序 „ 内排序 „ 整个排序过程在内存中完成 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 9 排序问题 „ 给定一个序列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 ，称为不增序 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 10 正序 vs. 逆序 „ “正序”序列 ：待排序序列正好符合 排序要求 „ “逆序” 序列 ：把待排序序列逆转过 来，正好符合排序要求 „ 例如，要求不升序列 „ 08 12 34 96 „ 96 34 12 08 逆序！ 正序！ 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 11 排序的稳定性 „ 稳定性 „ 存在多个具有相同排序码的记录 „ 排序后这些记录的相对次序保持不变 „ 例如，34 12 34’ 08 96 „ 08 12 34 34’ 96——稳定！ „ 08 12 34’ 34 96——不稳定！ 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 12 排序算法的衡量标准 „ 时间代价：记录的比较和移动次数 „ 空间代价 „ 算法本身的繁杂程度