1、 课程设计(论文) 题 目 名 称 几种常见的排序算法的实现与性能分析 课 程 名 称 数据结构课程设计 学 生 姓 名 学 号 系 、专 业 信息工程系、通信工程 指 导 教 师 2012 年 12 月 23 日 摘 要 设计一个测试程序比较起泡排序、直接排序、简单选择排序、快速排序、希尔 排序、堆排序算法的关键字比较次数和移动次数。运用多种自定义函数，通过在主 函数中调用自定义函数，实现其功能，最后输出相应算法的比较次数(至少有五种不 同的数据)和移动次数（关键字的交换记为三次移动） 。从而直观的判断各内部排序 算法性能的优劣性。 关键词：起泡排序；直接排序；简单选择排序；快速排序；希尔排
2、序；堆排序； 内部排序；直观；比较次数；移动次数 目录 1 问题描述 . 1 2 需求分析 . 1 3 概要设计 . 1 31 抽象数据类型定义. 1 32 模块划分 2 4 详细设计 3 41 数据类型的定义 3 42 主要模块的算法描述 . 3 5 测试分析 8 6 课程设计总结 12 参考文献 . 12 附录（源程序清单） 13 1 1 问题描述 设计一个测试程序比较起泡排序、直接排序、简单选择排序、快速排序、希尔 排序、堆排序算法的关键字比较次数和移动次数以取得直观感受。待排序表的表长 不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标有：关键 字参加比较次数和关键字的
3、移动次数（关键字交换记为3次移动）。最后输出比较 结果。 2 需求分析 （1）用数组S来存放系统随机产生的100个数据，并放到R数组中，数据由 程序随机产生，用户只需查看结果。 （2）利用全局变量times和changes来分别统计起泡排序、直接排序、简单 选择排序、快速排序、希尔排序、堆排序算法的比较次数和移动次数，然后输出结 果，并在每一次统计之后，将times和changes都赋值为0。 （3）在主函数中调用用户自定义函数，输出比较结果。 （4） 本程序是对几种内部排序算法的关键字进行性能分析的程序， 它分为以下 几个部分：a、建立数组；b、调用函数求比较和移动次数；c、输出结果。 3
4、概要设计 31 抽象数据类型定义 排序数据类型定义： ADT paixu 数据对象：D=aij|aij属于1，2，3,i,j0 数据关系：R=|ai-1,aiD，i=2,.,n 基本操作： Insertsort(); 初始条件：数组已经存在。 基本思想：将一个记录插入到已经排好序的有序列表中，从而得到了一个新的、 记录新增1的有序表。 2 Shellsort(); 初始条件：数组已经存在。 基本思想：先取定一个正整数d1Rj+gap) x=Rj;Rj=Rj+gap; Rj+gap=x; j=j-gap; changes+; else j=0; gap=gap/2; m+; 18 printf(“nn“); printf(“t最终排序结果为：“); for(i=1;i=1;i-)/将二叉树转换成堆 23 CreateHeap(i,L);/建堆 for(i
