数据结构--黄鑫海 (2)（精选）.doc

排序算法比较
——《数据结构》课程设计
院系名称:贵州航天职院技术学院
学生姓名: 黄鑫海
班级:09软件二班
小组成员:黄勰膀刘宏陈春
学号: A093GZ053020181
指导教师: 陆树芬
2011-6-1
目录
目录……………………………………………………
前言……………………………………………………
1设计思想…………………………………………….
2设计功能…………………………………………….
3功能实现…………………………………………….
4测试………………………………………………….
5小结………………………………………………….
6参考文献…………………………………………….
·前言:
计算机已经深入到人类社会的各个领域,其应用已经不再局限于科学计算,而更多用于控制,管理及数据处理等非数值计算的处理工作。另外,计算机加工处理的对象由纯粹的数值发展到字符,表格和图像等各种具有一定结构的数据,这就必须分析待处理对象的特性以及各处理对象之间存在的关系,而排序是其中必不可少的的一份子。所以展望计算机世界,数据结构是它的支持框架,而作为数据结构中的重要组成部分——排序,起作用是非同小可的。衡量数据结构的好坏其中有一个重要的指标,那就是时间复杂度。下面主要围绕各种排序及其时间的问题展开分析。

1设计思想:
:
排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列并计算其时间。内部排序算法主要分为5 大类,有十二个算法。插入排序类、交换排序类、选择排序类、归并排序类和基数排序类。算法主要包括:插入排序、折半插入排序、选择排序、冒泡排序、希尔排序、快速排序、堆排序、归并排序、基数排序等。
:
利用随机函数产生30000个随机整数,利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序,并统计每一种排序上机所花费的时间。
2设计功能:
1、冒泡排序属于稳定排序,是一种借助“交换”进行排序的方法。首先要将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两个记录交换之,然后比较第二个记录与第三个记录的关键字,以此类推,直至第n-1个记录与第n个记录的关键字进行比较为止,这一过程称为第一趟冒泡排序,其结果使得关键字最大的记录被安置在最后一个记录的位置上;然后进行第二趟冒泡排序,对前N-1个记录进行同样操作;以此类推,直到在一趟排序过程中没有进行过交换记录的操作为止。
2、直接插入排序属于稳定的排序,每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。第一趟将待比较的数值与它的前一个数值进行比较,当前一数值比待比较数值大的情况下继续循环比较,依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程,结束该次循环。
3、快速排序属于不稳定排序,是对起泡排序的一种改进。它的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。假设待排序的序列为{R.[s],R.[s+1],…….,R.[t]},首先任意选取一个记录,然后按下述原则从新排序记录:将关键字较他小的记录都安置在他的位置之前,将所有关键字较他大的记录都安置在他的位置后面。由此可以该“枢轴”记录最后所落的位置i作为分界线,将序列{R[s],R[s+1]…….R[t]}分割成两个子序列{R[s],R[s+1]…..R[i-1]}和{R[i+1]……R[t]},这个过程称作一趟快速排序。一趟快速排序的具体做法是:附设两个指针low和high,它们的初值分别指向数组第一个数据和最后一个数据,将枢轴记录暂存在R[0]的位置上排序过程中只作R[low]或R[high]的单向移动,直至一趟排序结束后再将枢轴记录移至正确位置上。
4、简单选择排序属于不稳定排序,基本思想是,每一趟在n-i+1(i=1,2,…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。第i趟简单选择排序是指通过n-i次关键字的比较,从n-i+1个记录中选出关键字最小的记录,并和第i个记录进行交换。共需进行n-1趟比较,直到所有记录排序完成为止。例如:进行第i趟选择时,从当前候选记录中选出关键字最小的k号记录,并和第i个记录进行交换。
5、希尔排序属于不稳定排序,也是一种属插入排序类,它的基本思想是:先将整个待排记录序列分割称为若干个子序列分别进行直接插入排序,待整个序列中记录“基本有序”时,再对全体记录进行一次直接插入排序。希尔排序的一个特点是:子序列的构成不是简单的“逐段分割”,而