发布时间 : 星期二 文章几种常见的排序算法的实现与性能分析数据结构课程设计报告更新完毕开始阅读a202d9189b6648d7c0c7464b
目录
1 问题描述 .................................................... 1 2 需求分析 .................................................... 1 3 概要设计 .................................................... 1 3．1抽象数据类型定义 ...................................... 1 3．2模块划分 .............................................. 3 4 详细设计 .............................................. 3
4．1数据类型的定义 ........................................ 3 4．2主要模块的算法描述 .................................... 4 5 测试分析 ............................................. 24 6 课程设计总结 ......................................... 30 参考文献 .............................................. 31 附录（源程序清单） ...................................... 32
1 问题描述
设计一个测试程序比较起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的关键字比较次数和移动次数以取得直观感受。待排序表的表长不小于100，表中数据随机产生，至少用5组不同数据作比较，比较指标有：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）。最后输出比较结果。
2 需求分析
当今社会，我们知道是信息化时代，那么排序算法对于计算机信息处理很重要，一个好的排序不仅可以使信息查找的效率提高，而且还直接影响着计算机的工作效率。目前，最常见的排序算法有直接排序法、希尔排序法、冒泡排序法、选择排序法、快速排序法、堆排序等算法。这些排序算法各有自己的优缺点，不同的排序算法适应不同的情况。就算法的整体性能而言,目前很难提出一种适应所有的排序场合的最好的排序算法，每种算法都有自己不同的适用场合。使用插入排序法，交换排序法，选择排序法设计与实现算法程序完成线性表的排序号。通过测试分析说明各排序算法的优缺点。通过实验结果分析，总结直接排序法、希尔排序法、冒泡排序法、选择排序法、快速排序法、堆排序等算法六类算法的特点。我们需要首先，用数组S来存放系统随机产生的100个数据，并放到R数组中，数据由程序随机产生，用户只需查看结果。然后，利用全局变量times和changes来分别统计起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法的比较次数和移动次数，然后输出结果，并在每一次统计之后，将times和changes都赋值为0。最后，在主函数中调用用户自定义函数，输出比较结果。
3 概要设计
3．1抽象数据类型定义
排序数据类型定义：
ADT paixu{
数据对象：D={aij|aij属于{1，2，3…},i,j>0}
1
数据关系：R={
Insertsort();
初始条件：数组已经存在。
基本思想：每一步将一个待排序的序列的记录，按其主关键的大小插入到前面已经排序的文件中适当的位置，知道全部插完为止。
Shellsort();
初始条件：数组已经存在。
基本思想：先取定一个正整数d1 Bubblesort(); 初始条件：数组已经存在。 基本思想：两两比较待排序记录的键值，并交换不满足顺序要求的那些偶对，直到全部满足顺序要求为止。 QuickSort(int low,int high)； 初始条件：数组已经存在。 基本思想：在待排序的n个记录中任取一个记录（通常取第一个记录），以该记录的键值为基准用交换的方法将所有记录分成两部分，所有键值比它小的安置在一部分，所有键值比它大的安置在另一部分，并把该记录排在两部分的中间，也就是该记录的最终位置。这个过程称为一趟快速排序。然后分别对所划分的两部分重复上述过程，一直重复到每部分内只有一个记录为止排序完成。 Selectsort(); 初始条件：数组已经存在。 基本思想：每次从待排序的记录中选出键值最小（或最大）的记录，顺序放在已排序的记录序列的最后，直到全部排完。对待排序的文件进行n-1趟扫描，第i趟扫描选出剩下的n-i+1个记录，并与第i个记录交换。 Heap(); 初始条件：数组已经存在。 基本思想：对一组待排序的的键值，首先是把它们按堆的定义排列成一个序列（称为初建堆），这就找到了最小键值，然后把最小的键值取出，用剩下的键值再重 2 建堆，便得到次小键值，如此反复进行，知道把全部键值排好序为止。 }ADT 排序 3．2模块划分 本程序包括两个模块： （1）主程序模块 void main() { 初始化； 随机数的产生； 调用子函数 }； （2）子函数模块：实现直接插入排序的抽象数据类型。 实现希尔排序的抽象数据类型。 实现冒泡排序的抽象数据类型。 实现快速排序的抽象数据类型。 实现选择排序的抽象数据类型。 实现堆排序的抽象数据类型。 最后输出相应算法的比较次数(至少有五种不同的数据)和移动次数（关键字的交换记为三次移动）。从而直观的判断各内部排序算法性能的优劣性。 4 详细设计 4．1数据类型的定义 (1)直接插入排序类型： void Insertsort(); (2)希尔排序类型： void Shellsort(); (3)冒泡排序类型： void Bubblesort(); (4)快速排序类型： void QuickSort(int low,int high); 3