排序综合数据结构课程设计论文

1、天津职业技术师范大学课 程 设 计 任 务 书 理 学院 数学0902 班 学生 （16）马新月 课程设计课题：16、综合排序： 利用随机函数随机产生N=200个随机整数，对这些数进行多种方法的排序。 要求：1）至少采用三种方法实现上述问题求解（插入排序、希尔排序、冒泡排序、快速排序、堆排序、归并排序）。把排序后的结果存在不同的文件中。 2）记录不同排序方法的运行时间，找出自己排序方法中最快的两种方法。 3）统计每种算法所用的比较次数和交换次数，以列表显示出来。一、课程设计工作日自 2012 年 2 月 21 日至 2012 年 3 月 4 日二、同组学生： 马新月 三、课程设计任务要求（包括

2、课题来源、类型、目的和意义、基本要求、完成时间、主要参考资料等）：课题来源：教师提供课题类型：设计课程设计的目的1) 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2) 使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3） 使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力1 天津职业技术师范大学课 程 设 计 评 审 表 学院 班 学生 设计任务完成情况及指导教师评语答辩情况评定成绩成绩： 指导教师签字： 日期： 教研室主任： 院长签字： 日期： 日期： 22- 22 -

3、1概要1.1设计目的 数据结构与算法课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构与算法是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。1）本演示程序对以下6种常用的内部排序算法进行实测比较：冒泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序；2）待

4、排序表的元素的关键字为整数。比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）；3）演示程序以以用户和计算机的对话方式执行，在计算机终端上显示提示信息，对随机数组进行排序，并输出比较指标值；4）最后对结果作出简单分析。1.2预期目标按要求输入不同的操作。输入后，根据不同的输入进行不同的操作，最终达到对各算法进行比较的目的。通过此次课程设计主要达到以下目的了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和

5、软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。2排序算法 2.1各排序算法的特点1）冒泡排序冒泡排序的基本概念是：依次比较相邻的两个数，将大数放在前面，小数放在后面。即首先比较第1个和第2个数，将大数放前，小数放后。然后比较第2个数和第3个数，将大数放前，小数放后，如此继续，直至比较最后两个数，将大数放前，小数放后，此时第一趟结束，在最后的数必是所有数中的最小数。重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再大于第2个数），将大数放前，小数放后，一直比较到最小数前的一对相邻数，将大数放前，小数放后，第二趟结束，在倒数第二

6、个数中得到一个新的最小数。如此下去，直至最终完成排序。由于在排序过程中总是大数往前放，小数往后放，相当于气泡往上升，所以称作冒泡排序。2）直接插入排序每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。3）简单选择排序（1）在一组元素ViVn-1中选择具有最小排序码的元素（2）若它不是这组元素中的第个元素，则将它与这一组元素中的第一个元素对调；（3）在这组元素中剔除这个具有最小排

7、序码的元素，在剩下的元素Vi+1Vn-1中重复执行第（1）（2）步，直到剩余元素只有一个为止。4）快速排序首先检查数据列表中的数据数，如果小于两个，则直接退出程序。如果有超过两个以上的数据，就选择一个分割点将数据分成两个部分，小于分割点的数据放在一组，其余的放在另一组，然后分别对两组数据排序；5） 希尔排序先取一个正整数d1n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止；6) 堆排序堆排序是一树形选择排序，在排序过程中，将R1.N看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子

8、结点之间的内在关系来选择最小的元素；堆的定义: N个元素的序列K1，K2，K3，.，Kn.称为堆，当且仅当该序列满足特性：KiK2i Ki K2i+1(1 I N/2)；2.2各算法的比较方法1.稳定性比较 插入排序、冒泡排序、简单选择排序及其他线形排序是稳定的 希尔排序、快速排序、堆排序是不稳定的2.时间复杂性比较 插入排序、冒泡排序、选择排序的时间复杂性为O(n2) 其它非线形排序的时间复杂性为O(nlog2n) 线形排序的时间复杂性为O(n);3.辅助空间的比较 线形排序的辅助空间为O(n),其它排序的辅助空间为O(1);4.其它比较插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有

9、序时，这种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了。当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下，宜用归并排序。当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序 3流程图及详细算法3.1流程图函数的调用关系图反映了演示程序的层次结构：HeapSortDisplayLTRandomNumInitLinkListBubb

10、leSortInsertSortSelectSortQuickSortShellSortmainstrand图3.1 流程图3.2流程图模块说明1）Main为主函数模块2）bubblesort，insertsort，selectsort，quicksort，shellsort，heansort分别对应冒泡排序，直接插入排序，简单选择排序，快速排序，希尔排序，堆排序的各函数模块3）在初始化数据之后，选择对应的排序模块进行排序，并对排序做出比较3.3可排序表的抽象数据类型定义：typedef struct /定义一个RedType型结构体，存放关键字 int key; /关键字为整型 RedTyp

11、e;class LinkList /定义一个顺序表public:RedType rMAXSIZE+1; /长度为MAXSIZE+1的数组r，数组里每个元素均为RedType int Length; /数组长度 int CmpNum, ChgNum; /关键字的比较次数，移动次数 LinkList(); /构造函数 bool LT(int i, int j); /比较i和j的大小 void Display(); /输出数组元素 void Insert( int dk); /插入排序 void ShellSort(); /希尔排序int Partition( int low, int high);

12、 /比基准小的数放左边，比起大的数放右边，返回基准位置 void QSort( int low, int high); /从low到high位置进行快速排序 void QuickSort(); /对有序表进行快速排序 void HeapAdjust( int s, int m); /将无序堆调整为大顶堆 void HeapSort(); /堆排序，将大顶堆转换为小顶堆 void BubbleSort(); /冒泡排序 int SelectMinKey( int k); /找到数组中最小值，返回最小值位置 void SelSort(); /对顺序表进行选择排序 void SelectSort()

13、; /界面设计void AllAbove(); /统计以上所有排序关键字的比较次数、移动次数及所消耗的时间;3.4程序代码3.4.1 函数声明#include #include #include #include #include #include #include #include #define MAXSIZE 1000#define TRUE 1#define FALSE 0typedef int BOOL;typedef struct int key; RedType;class LinkListpublic: RedType rMAXSIZE+1; int Length; int C

14、mpNum, ChgNum; LinkList(); bool LT(int i, int j); void Display(); void Insert( int dk); void ShellSort(); int Partition( int low, int high); void QSort( int low, int high); void QuickSort(); void HeapAdjust( int s, int m); void HeapSort(); void BubbleSort(); int SelectMinKey( int k); void SelSort();

15、 void SelectSort(); void AllAbove(); LinkList:LinkList() int i; for (i = 0; i = MAXSIZE; i+) ri.key = rand()%1000; Length=MAXSIZE+1; CmpNum=0; ChgNum=0; bool LinkList:LT(int i, int j) (CmpNum)+; if (i j) return TRUE; else return FALSE;void LinkList:Display()int j;for(int i=0;i=MAXSIZE;i+)coutsetw(6)

16、ri.key; if(+j%10=0)coutendl;coutendl;4.3.2六种排序算法代码/插入排序void LinkList:Insert(int dk) int i, j; RedType Temp; for (i = dk; i = 0 & LT(Temp.key, rj.key); j -= dk) (ChgNum)+; memcpy(&rj + dk, &rj, sizeof(RedType); memcpy(&rj + dk, &Temp, sizeof(RedType); /希尔排序void LinkList:ShellSort() int t=Length+1; do

17、 t=t/3+1; Insert( t); while(t1);/快速排序int LinkList:Partition(int low, int high) RedType Temp; int PivotKey; memcpy(&Temp, &rlow, sizeof(RedType); PivotKey = rlow.key; while (low high) while (low = PivotKey) high-; (CmpNum)+; (ChgNum)+; memcpy(&rlow, &rhigh, sizeof(RedType); while (low high & rlow.key

18、 = PivotKey) low+; (CmpNum)+; (ChgNum)+; memcpy(&rhigh, &rlow, sizeof(RedType); memcpy(&rlow, &Temp, sizeof(RedType); return low;void LinkList:QSort( int low, int high) int PivotLoc = 0; if (low high) PivotLoc = Partition( low, high); QSort(low, PivotLoc - 1); QSort( PivotLoc + 1, high); void LinkLi

19、st:QuickSort() QSort(0, Length - 1);/堆排序void LinkList:HeapAdjust(int s, int m) RedType Temp; int j = 0; s+; memcpy(&Temp, &rs - 1, sizeof(RedType); for (j = 2 * s; j = m; j *= 2) if (j = 0; i-) HeapAdjust(i, Length); for (i = Length; i 1; i-) memcpy(&Temp, &r0, sizeof(RedType); (ChgNum)+; memcpy(&r0

20、, &ri - 1, sizeof(RedType); memcpy(&ri - 1, &Temp, sizeof(RedType); HeapAdjust( 0, i - 1); /冒泡排序void LinkList:BubbleSort() int i, j; RedType temp; for (i = 1; i = MAXSIZE; i+) for (j = 1; j = MAXSIZE - i; j+) if (!LT(rj.key, rj + 1.key) (ChgNum)+; memcpy(&temp, &rj, sizeof(RedType); memcpy(&rj, &rj

21、+ 1, sizeof(RedType); memcpy(&rj + 1, &temp, sizeof(RedType); /选择排序int LinkList:SelectMinKey( int i) int Min = i; for (int k=i; k Length; k+) if (!LT(rMin.key, rk.key) Min = k; return Min;void LinkList:SelSort() int i, j; RedType temp; for (i = 0; i Length; i+) j = SelectMinKey( i); if (i != j) (Chg

22、Num)+; memcpy(&temp, &ri, sizeof(RedType); memcpy(&ri, &rj, sizeof(RedType); memcpy(&rj, &temp, sizeof(RedType); 4.3.3 排序算法的选择void LinkList:SelectSort() cout1. 插入排序endl; cout2. 希尔排序endl; cout3. 快速排序endl; cout4. 堆排序endl; cout5. 冒泡排序endl; cout6. 选择排序endl; cout7. 以上各种排序endl; cout8. 退出程序endl; cout请选择需要进

23、行的操作:endl;void LinkList:AllAbove() int TempTime; int SpendTime; coutendl; LinkList(); cout插入排序:endl; TempTime = (int)GetTickCount(); Insert( 1); SpendTime = (int)GetTickCount() - TempTime; coutendl; coutCompareNumber=CmpNum ChageNumber=ChgNum TimeSpent=SpendTimemsendl; LinkList();/随机数列复位 coutendl; c

24、out希尔排序:endl; TempTime = (int)GetTickCount(); ShellSort(); SpendTime = (int)GetTickCount() - TempTime; coutendl; coutCompareNumber=CmpNum ChageNumber=ChgNum TimeSpent=SpendTimemsendl; LinkList();/随机数列复位 coutendl; cout快速排序:endl; TempTime = (int)GetTickCount(); QuickSort(); SpendTime = (int)GetTickCou

25、nt() - TempTime; coutendl; coutCompareNumber=CmpNum ChageNumber=ChgNum TimeSpent=SpendTimemsendl; LinkList();/随机数列复位 coutendl; cout堆排序:endl; TempTime = (int)GetTickCount(); HeapSort(); SpendTime = (int)GetTickCount() - TempTime; coutendl; coutCompareNumber=CmpNum ChageNumber=ChgNum TimeSpent=SpendTi

26、memsendl; LinkList();/随机数列复位 coutendl; cout冒泡排序:endl; TempTime = (int)GetTickCount(); BubbleSort(); SpendTime = (int)GetTickCount() - TempTime; coutendl; coutCompareNumber=CmpNum ChageNumber=ChgNum TimeSpent=SpendTimemsendl; LinkList();/随机数列复位 coutendl; cout选择排序:endl; TempTime = (int)GetTickCount();

27、 SelSort(); SpendTime = (int)GetTickCount() - TempTime; coutendl; coutCompareNumber=CmpNum ChageNumber=ChgNum TimeSpent=SpendTimemsselect; switch (select) case 1: cout插入排序前:endl;L.Display(); cout插入排序后:endl; TempTime = (int)GetTickCount(); L.Insert(1); SpendTime = (int)GetTickCount() - TempTime; L.Di

28、splay();coutendl; cout比较次数=L.CmpNum 关键字移动次数=L.ChgNum 所需时间=SpendTimemsendl; break; case 2:cout希尔排序前:endl; L.Display(); cout希尔排序后:endl;coutendl; TempTime = (int)GetTickCount(); L.ShellSort(); SpendTime = (int)GetTickCount() - TempTime; L.Display();coutendl; cout比较次数=L.CmpNum 关键字移动次数=L.ChgNum 所需时间=Spen

29、dTimemsendl; break; case 3:cout快速排序前:endl;L.Display(); cout快速排序后:endl; TempTime = (int)GetTickCount(); L.QuickSort(); SpendTime = (int)GetTickCount() - TempTime; L.Display(); coutendl; cout比较次数=L.CmpNum 关键字移动次数=L.ChgNum 所需时间=SpendTimemsendl; break; case 4:cout堆排序前:endl; L.Display();cout堆排序后:endl; Te

30、mpTime = (int)GetTickCount(); L.HeapSort(); SpendTime = (int)GetTickCount() - TempTime; L.Display(); coutendl; cout比较次数=L.CmpNum 关键字移动次数=L.ChgNum 所需时间=SpendTimemsendl; break; case 5: cout冒泡排序前:endl;L.Display();cout冒泡排序后:endl; TempTime = (int)GetTickCount(); L.BubbleSort(); SpendTime = (int)GetTickCo

31、unt() - TempTime; L.Display(); coutendl; cout比较次数=L.CmpNum 关键字移动次数=L.ChgNum 所需时间=SpendTimemsendl; break; case 6: cout选择排序前:endl; L.Display();cout选择排序后:endl; TempTime = (int)GetTickCount(); L.SelSort(); SpendTime = (int)GetTickCount() - TempTime; L.Display(); coutendl; cout比较次数=L.CmpNum 关键字移动次数=L.Chg

32、Num 所需时间=SpendTimemsendl; break; case 7: L.AllAbove(); break; default:coutplease input numbers againendl;break; while(select!=8); 4运行结果 4.1调试分析1对正序、逆序和若干不同程度随机打乱的可排序表，进行各种排序方法的比较测试，得到的测试数据具有较好的典型性和可比较性。通过设计和实现指定程序的随机乱序算法，对伪随机数序列的产生有了具体的认识和实践。2将排序算法中的关键字比较和交换分别由Less和Swap两个内部操作实现，较好的解决了排序算法的关键字比较次数和移动

33、次数的统计问题。而赋值是直接统计的。3本实习作业采用循序渐进的策略，首先设计和实现可排序表的建立和随机操作，然后用插入排序验证各种内部辅助操作的正确性，进而逐个加入其他排序算法，最后完成对测试结果的显示。调试能力有了提高。4.2输入输出1进入程序后即显示文本方式的用户界面：图5.1 进入程序后的界面2开始运行时的用户界面：1）输入1回车，即得直接插入排序的排序结果及其关键字比较次数和移动次数和时间。如图5.2：图5.2 输入1后的运行结果2）输入2回车，即得希尔排序的排序结果及其关键字比较次数和移动次数及时间，如图5.3：图5.3 输入2后的运行结果3）输入3回车，即得快速排序的排序结果及其关

34、键字比较次数和移动次数及时间，如图5.4：图5.4 输入3后的运行结果4）输入4回车，即得堆排序的排序结果及其关键字比较次数和移动次数及时间，如图5.5：图5.5 输入4后的运行结果5）输入5回车，即得冒泡排序的排序结果及其关键字比较次数和移动次数及时间，如图5.6：图5.6 输入5后的运行结果6）输入6回车，即得选择排序的排序结果及其关键字比较次数和移动次数及时间，如图5.7：图5.7 输入6后的运行结果7）输入7回车，即得以上所有排序的排序结果及其关键字比较次数和移动次数及时间，如图5.8：图5.8 输入7后的运行结果8）输入8回车，即退出该程序。4.3排序算法的评价对各种表长和测试组数进行了测试，程序运行正常。分析实测得到的数值，6种排序算法（快速排序采用“比中法”）的特点小结如下：测试插入排序希尔排序快速排序堆排序冒泡排序选择排序比较次数第三多越乱（逆）越多少乱否差异小少乱否差异小稍多乱否差异很小最多越乱（逆）越多越乱（逆）越多第二多与乱否无关移动次数第二多越乱（逆）越多约为快速排序的两倍第二少乱否差异较小稍多乱否差异很小最多越乱（逆）越多最少正和逆序少 (1)若n较小(如n50)，可采用直接插入或直接选择排序。当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。(2)若文件初始状态基本有序(指正