数据结构课程设计——排序算法比较 第 1 页 共 2 0 页 XXXXXX 大学 《数据结构》课程设计报告 数据结构课程设计——排序算法比较 第 2 页 共 2 0 页 目 录 排序算法比较 一、需求分析 二、程序的主要功能 三、程序运行平台 四、数据结构 五、算法及时间复杂度 六、测试用例 七、程序源代码 二 感想体会与总结 数据结构课程设计——排序算法比较 第 3 页 共 20 页 排序算法比较 一、需求分析 利用随机函数产生 N 个随机整数（N = 500，1000，1500，2000，2500，…,30000），利用直接插入排序、折半插入排序，起泡排序、快速排序、选择排序、堆排序，基数排序七种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间（统计为图表坐标形式）。 二、程序的主要功能 1.用户输入任意个数，产生相应的随机数 2.用户可以自己选择排序方式（直接插入排序、折半插入排序、起泡排序、快速排序、选择排序、堆排序、基数排序）的一种 3.程序给出原始数据、排序后从小到大的数据，并给出排序所用的时间。 三、程序运行平台 Visual C++ 6.0 版本 四、数据结构 本程序的数据结构为线形表，线性顺序表、线性链表。 。 1、结构体： typedef struct { int *r; //r 指向线形表的第一个结点。 r[0]闲置，不同的算法有不同的用处，如用作哨兵等。 int length; //顺序表的总长度 }Sqlist; 2、空线性表 Status InitSqlist(Sqlist &L) { L.r=(int *)malloc(MAXSIZE*sizeof(int)); //分配存储空间 if(!L.r) { printf("存储分配失败！"); exit(0); } //存储分配失败 数据结构课程设计——排序算法比较 第 4 页 共 20 页 L.length=0;//初始长度为 0 return OK; } 五、算法及时间复杂度 （一）各个排序是算法思想： （1）直接插入排序：将一个记录插入到已排好的有序表中，从而得到一个新的，记录数增加 1 的有序表。 （2）折半插入排序：插入排序的基本插入是在一个有序表中进行查找和插入，这个查找可利用折半查找来实现，即为折半插入排序。 （3）起泡排序：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直到第 N-1 和第 N 个记录的关键字进行过比较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个...
