怎样研究算法-排序算法研究示例.pdf

为什么要研究排序算法 --结构化数据表查找问题 战德臣 哈尔滨工业大学 教授.博士生导师 教育部大学计算机课程教学指导委员会委员 OKOK ZhanDCZhanDC Research Center on Intelligent Computing for Enterprises Services, Harbin Institute of Technology 为什么要研究排序算法--结构化数据表查找问题 (1)什么是排序问题? 战德臣教授 排序问题 对一组对象按照某种规则进行有序排列。通常是把一组对象整 理成按关键字递增(或递减) 的排列，关键字是指对象的一个用 于排序的特性。 例如： 对一组“人”，按“年龄”或“身高”排序； 对一组“商品”，按“价格”排序； 对一组“网页”，按“重要度”排序； 对一组“词汇”，按“首字母”字典序排序。 …… 为什么要研究排序算法--结构化数据表查找问题 (2)为什么要研究排序问题? 战德臣教授 结构化数据表的查找问题 查找成绩为80分的所有同学? 未排序 学号 姓名 成绩 120300101 李鹏 88 【算法A ：未排序数据查找算法】 120300105 张伟 66 Start of algorithm 120300107 闫宁 95 120300102 王刚 79 Step 1. 从数据表的第1条记录开始，直到其最后一 120300103 李宁 94 条记录为止，读取每一条记录，做Step 2。 120300106 徐月 85 120300108 杜岩 44 Step 2. 对每一条记录，判断成绩是否等于给定的分 120300104 赵凯 69 数：如果是，则输出；如果不是，则不输出。 120300109 江海 77 120300110 周峰 73 End of algorithm 数据表记录数: n 算法效率：读取并处理所有记录，即n条记录 为什么要研究排序算法--结构化数据表查找问题 (2)为什么要研究排序问题? 战德臣教授 结构化数据表的查找与统计需要排序 查找成绩为80分的所有同学? 已排序 学号 姓名 成绩 【算法B：已排序数据查找算法】 120300107 闫宁 95 120300103 李宁 94 Start of algorithm 120300101 李鹏 88 Step 1. 从数据表的第1条记录开始，直到其最后一条 120300106 徐月 85 记录为止，读取每一条记录，做Step 2和Step 3步。 120300102 王刚 79 120300109 江海 77 Step 2. 对每一条记录，判断成绩是否等于给定的分 120300110 周峰 73 数：如果等于，则输出；如果不等于，则不输出。 120300104 赵凯 69 120300105 张伟 66 Step 3. 判断该条记录的成绩是否小于给定的分数： 120300108 杜岩 44 如果不是，则继续；否则，退出循环，算法结束。 数据表记录数: n End of algorithm 算法效率：读取并处理部分记录，即=n条记录 为什么要研究排序算法--结构化数据表查找问题 (2)为什么要研究排序问题? 战德臣教授 结构