《计算机软件基础》第四章 查找与排序（4-8）多关键字排序（2/2）

48多关键字排序 一.问题特点: 1排序关键字不止一个; 2.排序关键字级别高低不同; 3.人工方法的处理过程不便于在计算机 上实现

4.8 多关键字排序 一. 问题特点： 1.排序关键字不止一个； 2. 排序关键字级别高低不同； 3.人工方法的处理过程不便于在计算机 上实现。    

学生成绩表 学号姓名数学英语语文总分 1张三808080240 2李四707070210 18王五908070240 30赵六907080240 4(》

学号 姓名 数学 英语 语文 总分 1 张三 80 80 80 240 2 李四 70 70 70 210 … … … … … … 18 王五 90 80 70 240 … … … … … … 30 赵六 90 70 80 240 学生成绩表    

人工万法的处理过程: 按级别从高到低的次序对不同关键 字进行排序。在排序过程中若发现有 高关键字值相同的记录,再对这些记 录按级别较低的关键字进行排序 人工方法的处理过程在计算机上实 现的主要难点: 按不同关键字排序的记录个数不同

❖ 人工方法的处理过程在计算机上实 现的主要难点： 按不同关键字排序的记录个数不同 。 ❖ 人工方法的处理过程： 按级别从高到低的次序对不同关键 字进行排序。在排序过程中若发现有 高关键字值相同的记录，再对这些记 录按级别较低的关键字进行排序 。    

令计算机处理方法的出发点: 为了便于算法在计算机上的实现,应该 使按照不同关键字排序的对象都相同(整个 线性表中的所有记录)。 令计算机处理方法的实现难点: 1.排序关键字的顺序如何安排? 2.怎样在高关键字相同时由低关键字的值决 定记录的次序?

❖ 计算机处理方法的出发点： 为了便于算法在计算机上的实现，应该 使按照不同关键字排序的对象都相同（整个 线性表中的所有记录）。 ❖ 计算机处理方法的实现难点： 1. 排序关键字的顺序如何安排？ 2. 怎样在高关键字相同时由低关键字的值决 定记录的次序？    

◇计算机处理方法的解决思路: 1.先按级别低的关键字进行排序,后按级别 高的关键字进行排序; 2除第一次排序外,其余各次排序均必须采 用稳定的排序算法。 为什么 4) p

1.先按级别低的关键字进行排序，后按级别 高的关键字进行排序； 2.除第一次排序外，其余各次排序均必须采 用稳定的排序算法。 ❖ 计算机处理方法的解决思路：    

学生成绩表 学号姓名数学英语语文总分 1张三808080240 2李四707070210 18王五908070240 30赵六907080240 4(》

学号 姓名 数学 英语 语文 总分 1 张三 80 80 80 240 2 李四 70 70 70 210 … … … … … … 18 王五 90 80 70 240 … … … … … … 30 赵六 90 70 80 240 学生成绩表    

按英语成绩排序后的结果: 学号姓名数学英语语文总分 1张三808080240 18王五908070240 2李四707070210 30赵六907080240 4(》

学号 姓名 数学 英语 语文 总分 1 张三 80 80 80 240 18 王五 90 80 70 240 … … … … … … 2 李四 70 70 70 210 … … … … … … 30 赵六 90 70 80 240 按英语成绩排序后的结果：    

按数学成绩排序后的结果: 学号姓名数学英语语文总分 18王五908070240 30赵六907080240 1张三808080240 2李四707070210 4(》

学号 姓名 数学 英语 语文 总分 1 张三 80 80 80 240 18 王五 90 80 70 240 … … … … … … 2 李四 70 70 70 210 … … … … … … 30 赵六 90 70 80 240 按数学成绩排序后的结果：    

按总分排序后的结果: 学号姓名数学英语语文总分 18王五908070240 30赵六907080240 1张 80 80 80240 2李四707070210 4(》

学号 姓名 数学 英语 语文 总分 1 张三 80 80 80 240 18 王五 90 80 70 240 … … … … … … 2 李四 70 70 70 210 … … … … … … 30 赵六 90 70 80 240 按总分排序后的结果：    

◇计算机处理方法的解决思路: 1.排序关键字从低到高,保证最终的顺序由 级别高的关键字决定。 2.后面各次选择稳定的排序算法保证在高关 键字值相同时记录排列顺序由低关键字的排 列结果决定

1. 排序关键字从低到高，保证最终的顺序由 级别高的关键字决定。 2. 后面各次选择稳定的排序算法保证在高关 键字值相同时记录排列顺序由低关键字的排 列结果决定。 ❖ 计算机处理方法的解决思路：    