1
实验五：查找排序
实验环境
Air 15 ＋ Win 10＋ VS2019
学号姓名
2
一．实验项目要求
实验目的：
1．掌握哈希表的定义，哈希函数的构造方法。
2．掌握并比较各种排序算法。
3. 掌握查找的概念、静态查找与动态查找、顺序查找、二分查找、
索引查找等算法思想。
4. 掌握二叉排序树的概念、平衡二叉树等算法思想。
5. 掌握哈希查找、直接插入排序、快速排序、冒泡排序、简单选择
排序等算法思想。
实验内容：
设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、
成绩等信息。要求实现以下功能：
1、查找：分别给定学生学号、姓名，能够查找到学生的基本信息
（要求至少实现改进后的顺序查找算法）；
2、排序：分别按学生的学号、成绩进行排序（要求至少用实现直接
插入排序、冒泡排序、简单选择排序算法）。
2
二．理论分析或算法分析（含实验项目要求的分析、数学或逻辑推导等）
1、查找和排序是日常数据处理过程中经常要进行的操作和运算。
2、查找是根据给定的某个值，在查找表中确定一个其关键字等于给
定值的数据元素或(记录)。若查找表中存在这样一个记录，则称“查找
成功”，查找结果：给出整个记录的信息，或指示该记录在查找表中的
位置；否则称“查找不成功”，查找结果：给出“空记录”或“空指
针”。
3、静态查找与动态查找的区别。平均查找长度。
4、查找算法有：
静态查找中常见的查找算法：顺序查找、二分查找、索引查找。动
态查找中常见的算法有二叉排序树和平衡二叉树上的查找。平均查找长
度为 0 的哈希查找。
5、 排序是是将一组“无序”的记录序列调整为“有序”的记录序
列。
6、 排序算法的优劣从空间复杂度、时间复杂度、稳定性三个角度
分析。
7、 常见的排序算法可分为：插入类、交换类、选择类、归并排序、
基数排序等。
