几种常见的排序算法的实现与性能分析数据结构课程设计报告Word格式.docx

1、b、挪用函数求比较和移动次数；c、输出结果。3 概要设计31抽象数据类型概念排序数据类型概念：ADT paixu数据对象：D=aij|aij属于1，2，3,i,j0数据关系：R=|ai-1,aiD，i=2,.,n大体操作：Insertsort（）;初始条件：数组已经存在。大体思想：将一个记录插入到已经排好序的有序列表中，从而取得了一个新的、记录新增1的有序表。 Shellsort（）;先取定一个正整数d1n,把全数记录分成d1个组，所有距离为d1倍数的记录放在一组中，在各组内进行插入排序，然后取d2d1重复上述分组和排序工作，直至取di=1,即所有记录放在一个组中排序为止。Bubblesort

2、（）;两两比较待排序记录的键值，并互换不知足顺序要求的那些偶对，直到全数知足顺序要求为止。QuickSort（int low,int high）；在待排序的n个记录中任取一个记录（通常取第一个记录），以该记录的键值为基准用互换的方式将所有记录分成两部份，所有键值比它小的安置在一部份，所有键值比它大的安置在另一部份，并把该记录排在两部份的中间，也确实是该记录的最终位置。那个进程称为一趟快速排序。然后别离对所划分的两部份重复上述进程，一直重复到每部份内只有一个记录为止排序完成。Selectsort（）;每次从待排序的记录当选出键值最小（或最大）的记录，顺序放在已排序的记录序列的最后，直到全数排完。

3、对待排序的文件进行n-1趟扫描，第i趟扫描选出剩下的n-i+1个记录，并与第i个记录互换。Heap（）;对一组待排序的的键值，第一是把它们按堆的概念排列成一个序列（称为初建堆），这就找到了最小键值，然后把最小的键值掏出，用剩下的键值再重建堆，便取得次小键值，如此反复进行，明白把全数键值排好序为止。ADT 排序32模块划分本程序包括两个模块：（1）主程序模块void main（）初始化；随机数的产生；挪用子函数；（2）子函数模块：实现直接插入排序的抽象数据类型。 实现希尔排序的抽象数据类型。 实现冒泡排序的抽象数据类型。 实现快速排序的抽象数据类型。 实现选择排序的抽象数据类型。 实现堆排序的抽

4、象数据类型。最后输出相应算法的比较次数（至少有五种不同的数据）和移动次数（关键字的互换记为三次移动）。4 详细设计41数据类型的概念（1）直接插入排序类型：void Insertsort（）;（2）希尔排序类型：void Shellsort（）;（3）冒泡排序类型：void Bubblesort（）;（4）快速排序类型：void QuickSort（int low,int high）;（5）选择排序类型：void Selectsort（）;（6）堆排序类型：void Heap（）;42要紧模块的算法描述下面是主程序的结构图和几个要紧模块的流程图：开始 循环产生一组随机数将随机数保存在数组中堆排

5、序选择排序快速排序起泡排序希尔排序插入排序记录关键字的比较次数和移动次数输出关键字的比较次数和移动次数结束 主程序结构图 输入要排序的一组元素i=1,j=1定义临时中间变量k，并赋初值i元素总个数 Ni+1j第j+1个元素 Y N利用k交换第j个元素和第j+1个元素 Y输出比较次数和移动次数冒泡排序关键字比较次数和移动次数的流程图i=1，j=1定义临时中间变量h，并赋初值元数总个数做第i趟排序 Yi=i+1在无序区Ri-n中选h最小记录Rhh记下目前找到的最小关键字所在的位置交换Ri和Rh 选择排序关键字比较次数和移动次数的流程图将二叉树转换成堆i=总元素个数-1=1将堆的根植和最后一个值交换

6、i-,k+堆排序关键字比较次数和移动次数的流程图5 测试分析进行了99趟排序后，取得了最终的排序结果，而且也明白了直接插入排序的比较次数和移动次数了解了直接插入排序的性能后，下面是希尔排序的性能比较：了解了希尔排序的性能后，下面是冒泡排序的性能比较：了解了冒泡排序的性能后，下面是快速排序的性能比较：了解了快速排序的性能后，下面是选择排序的性能比较：了解了选择排序的性能后，下面是堆排序的性能比较：以上确实是对六种排序算法的一种演示，通过观看和分析咱们能够比较六种排序的性能。6 课程设计总结通过本次课程设计，我对直接插入排序，希尔排序，选择排序等六种排序的概念有了一个新的熟悉，也慢慢地体会到了它们

7、之间的微妙。这次的课程设计，增强了我的动手，试探和解决问题的能力。巩固和加深了我对数据结构的明白得，也让我知道了理论与实际相结合是超级重要的，更让我进一步明白了“团结确实是力量”这句话的含义。在整个设计进程中，构思是很花时刻的。调试时常常会碰到如此那样的错误，有的是因为粗心造成的语法错误。固然，很多是因为用错了方式，老是实现不了。同时在设计进程中发觉了自己的不足的地方，对以前所学过的知识明白得的不够深刻，把握的不够透彻。依照我在课程设计中碰到的问题，我将在以后的学习进程中注意以下几点：一、多在实践中锻炼自己；二、写程序的进程中要考虑周到；3、在做设计的时候要有信心，有耐心，切勿急躁。这次的课程

8、设计得以顺利完成，与黄同成教师的耐心指导和同窗们的及时帮忙是分不开的。当我在编写程序碰到难题时，是黄教师的耐心指导，我才能够冲破一个个难关。在程序设计进程中，同窗们给我的鼓舞和帮忙使我信心倍增。在此我再次向黄同成教师和热心帮忙我的同窗表示深深的谢意。参考文献1 黄同成，黄俊民，董建寅数据结构M北京：中国电力出版社，20202 董建寅，黄俊民，黄同成数据结构实验指导与题解M北京：3 严蔚敏，吴伟民. 数据结构（C语言版）M. 北京：清华大学出版社，20024 刘振鹏，张晓莉，郝杰数据结构M北京：中国铁道出版社，2003 附录（源程序清单）#include #define L 100#define

9、 FALSE 0#define TRUE 1/*typedef struct int key; char otherinfo;RecType;*/.）; q=getchar（）; if （q!=xA） getchar（）;ch1=n; void Insertsort（）/直接插入排序 int i,j,k,m=0; printf（ntt尚未排序的数据为（回车继续）： for（k=1;k=L;k+）%5d,Rk）;n for（i=2;i+） if（RiRi-1） R0=Ri;j=i-1; while（R00） for（i=gap+1; j=i-gap; while（j if （RjRj+gap）

10、x=Rj;Rj=Rj+gap; Rj+gap=x; j=j-gap; else j=0; gap=gap/2;nt希尔排序的比较次数为%dnt希尔排序的移动次数为%dvoid Bubblesort（）/冒泡排序 int i,j,k; int exchange; exchange=FALSE; for（j=L;j=i+1;j-） if（RjRj-1） R0=Rj; Rj=Rj-1; Rj-1=R0; exchange=TRUE; changes+=3; if（exchange）; nt冒泡排序的比较次数为%dnt冒泡排序的移动次数为%dint Partition（int i,int j） /快速

11、排序 int pirot=Ri; while（i=pirot） j-; if（i Ri+=Rj;Ri i+; Rj-=Ri; Ri=pirot; return i;void QuickSort（int low,int high） int pirotpos,k,i; if （lowhigh） pirotpos=Partition（low,high）; num+; QuickSort（low,pirotpos-1）; QuickSort（pirotpos+1,high）;printf（nt快速排序的比较次数为%dnt快速排序的移动次数为%dtimes=0;changes=0;void Select

12、sort（） /选择排序 int i,j,k,h; h=i; for（j=i+1;j+） times+; if （RjRh） h=j; if（h!=j） R0=Rh;Rh=Ri;Ri=R0;nt选择排序的比较次数为%dvoid CreateHeap（int root,int index）/建堆 int j,temp,finish; j=2*root; temp=Rroot; finish=0; while （j=index&finish=0） if （j=Rj） finish=1; /堆成立完成 Rj/2=Rj;/父结点=当前结点 j=j*2; Rj/2=temp; /父结点=root值void HeapSort（） int i,j,temp,k; for（i=（L/2）;i=1;i-）/将二叉树转换成堆 CreateHeap（i,L）;/建堆 for（i=L-1,k=1;i-,k+） temp=Ri+1;/堆（heap）的root值和最后一个值互换 Ri+1=R1; R1=temp; CreateHeap（1,i）;void Heap（） int k; printf（nt HeapSort（）;nt堆排序的比较次数为%dnt堆排序的移动次数为%d