1、数据结构数据结构 课程设计报告课程设计报告 1. 题目题目 排序排序 2. 需求分析需求分析 2.12.1、选题要求、选题要求 （1）设计一个菜单，格式如下： 1.直接插入排序 2.希尔排序 3.冒泡排序 4 快速排序 5 选择排序 6.堆排序 7.退出程序 （2）选择不同的菜单进行相应的排序，并给出排序的关键字序列。 2.22.2、选题的意义及背景、选题的意义及背景 排序是计算机程序设计中的一种重要操作。 它的功能是将一个数 据元素的任意序列，重新排列成一个按关键字有序的序列。 排序的方法很多，但是就其全面性能而言， 很难提出一种被认为 1 是最好的方法， 每一种方法都有各自的优缺点，适合在
2、不同的环境下 使用。如果按排序过程中依据的不同原则对内部排序方法进行分类， 则大致可分为插入排序，交换排序，选择排序，归并排序和记数排序 等五类。 此实验通过对直插排序、希尔排序、冒泡排序、快速排序、选择 排序、堆排序这几种内部排序算法进行比较，能使我们更好的掌握这 些排序的基本思想及排序算法。通过该题目的设计过程， 可以加深理 解各种数据结构的逻辑结构、 存储结构及相应上运算的实现，进一步 理解和熟练掌握课本中所学的各种数据结构， 学会如何把学到的知识 用于解决实际问题，培养我们的动手能力。 2.32.3、课程设计目标、课程设计目标 本课程设计对以下内部排序算法进行比较： 直插排序、 希尔排
3、序、 冒泡排序、快速排序、选择排序、堆排序。 待排序表的元素关键字为整数， 用随机不同的测试数据做测试比 较。 比较的指标为关键字的比较次数、 关键字的移动次数和所用时间。 最后对这些内部排序算法进行性能分析。 3. 概要设计概要设计 3.13.1、原始数据、原始数据 用户输入记录的个数，数据由随机数产生器生成。 3.23.2、输出数据、输出数据 产生的随机数分别用直插排序、 希尔排序、 冒泡排序、 快速排序、 选择排序、 堆排序。 这些排序方法进行排序， 输出关键字的比较次数、 2 移动次数和所用时间。 3.33.3、数据处理、数据处理 3.33.3、存储结构存储结构 主程序主程序 产生一组
4、产生一组 随机数随机数 将 随 机 数 保将 随 机 数 保 存在数组中存在数组中 直插排直插排 序序 希尔排希尔排 序序 冒泡排冒泡排 序序 快速排快速排 序序 选择排选择排 序序 堆排序堆排序 记录关键字的比较次数、记录关键字的比较次数、 移动次数和所用时间移动次数和所用时间 输出关键字的比较次数、输出关键字的比较次数、 移动次数的平均值移动次数的平均值 循环循环 3 typedef structtypedef struct int key;int key; RedType; RedType; 4. 详细设计详细设计 4.1、各排序算法的各排序算法的基本思想基本思想 1）直接插入排序 每次
5、从无序表中取出第一个元素， 把它插入到有序表的合适 位置，使有序表仍然有序。第一趟比较前两个数,然后把第二个数 按大小插入到有序表中; 第二趟把第三个数据与前两个数从后向 前扫描，把第三个数按大小插入到有序表中；依次进行下去，进 行了(n-1)趟扫描以后就完成了整个排序过程。 2） 希尔排序 先取一个正整数 d11); /快速排序快速排序 int LinkList:Partition(int low, int high) RedType Temp; int PivotKey; memcpy( PivotKey = rlow.key; while (low 1; i-) memcpy( (Chg
6、Num)+; memcpy( memcpy( HeapAdjust( 0, i - 1); /冒泡排序冒泡排序 void LinkList:BubbleSort() int i, j; RedType temp; for (i = 1; i select; switch (select) case 1: cout“插入排序前:“endl; L.Display(); cout“插入排序后:“endl; TempTime = (int)GetTickCount(); L.Insert(1); SpendTime = (int)GetTickCount() - TempTime; L.Display(); coutendl; cout“ 比 较 次 数 =“L.CmpNum“ “ 关 键 字 移 动 次 数 =“L.ChgNum“ “所需时间=“SpendTime“ms“endl; break; case 2: cout“希尔排序前:“endl; L.Display(); cout“希尔排序后:“endl; coute
