排序算法比较

《排序算法比较》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、排序算法比较一、课程设计目的学习和巩固数据结构的基本知识。体会在程序设计中数据的重要作用，学会在程序设计中运用数据结构的相关知识解决问题。将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际，实践编程的能力。具体来说，掌握各种排序的基本思想﹑掌握各种排序方法的算法实现﹑掌握各种排序方法的优劣分析及花费的时间的计算。二、设计内容和要求利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间。三、工程进度及个人任务（1）工程进度：2014.1.1

2、—1.3选题，编写种排序函数。2014.1.6—1.9为了不使每次排序都要重新生成带排序的数，查找资料编写如何使程序实现将生成的数都保存到.txt文件中，以后排序后的数也都保存到.txt文件中。2014.1.10—1.11组合程序，并调试。2014.1.12完成设计报告。（2）个人任务:谢奇恩-完成各种排序函数的编写及最后的课程报告；韩海真（组长）—实现程序整合优化及调试。四、数据定义用顺序表作为文件的存储结构，并且按关键字递增排序其存储类型说明如下：#defineMAX60000//记录数组的最大值typedefintdatatype;//定义关键字类型typedefs

3、truct{intkey;//记录的关键字域datatypeother;//记录的其它字域}rectype;16rectyper[MAX],*s;//将生产的30000个随机数放到r[MAX]数组存放原始数据，*s存放排//序后的数据数据输入输出：由随机函数生产30000个随机数，分别用直接插入排序；直接选择排序；起泡排序；希尔排序；快速排序；堆排序这些排序方法进行排序，输出每种排序的实际运行时间，将排好的数存放在.txt文档中。五、各种排序的基本原理及时间复杂度分析1、直接插入排序（Insert_Sort）（1）基本原理：假设待排序的n个记录{R0，R1，…，Rn}顺序

4、存放在数组中，直接插入法在插入记录Ri(i=1，2，…，n-1)时，记录被划分为两个区间[R0,Ri-1]和[Ri+1,Rn-1],其中，前一个子区间已经排好序，后一个子区间是当前未排序的部分，将关键码Ki与Ki-1Ki-2，…，K0依次比较，找出应该插入的位置，将记录Ri插，然后将剩下的i-1个元素按关键词大小依次插入该有序序列，没插入一个元素后依然保持该序列有序，经过i-1趟排序后即成为有序序列。每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。（2）时间复杂度分析：直接插入排序算法必须进行n-1趟。最好情况下，

5、即初始序列有序，执行n-1趟，但每一趟只比较一次，移动元素两次，总的比较次数是(n-1)，移动元素次数是2(n-1)。因此最好情况下的时间复杂度就是O(n)。最坏情况(非递增)下，最多比较i次，因此需要的比较次数是：所以，时间复杂度为O(n2)。2、直接选择排序（Select_Sort）（1）基本原理：待排序的一组数据元素中，选出最小的一个数据元素与第一个位置的数据元素交换；然后在剩下的数据元素当中再找最小的与第二个位置的数据元素交换，循环到只剩下最后一个数据元素为止，依次类推直到所有记录。第一趟第n个记录中找出关键码最小的记录与第n个记录交换；第二趟，从第二个记录开始的

6、，2-1个记录中再选出关键码最小的记录与第二个记录交换；如此，第i趟，则从第i个记录开始的n-i+l个记录中选出关键码最小的记录与第i个记录交换，直到所有记录排好序。（2）时间复杂度分析：该算法运行时间与元素的初始排列无关。不论初始排列如何，该算法都必须执行n-1趟，每趟执行n-i-1次关键字的比较，这样总的比较次数为：所以，简单选择排序的最好、最坏和平均情况的时间复杂度都为O(n2)。3、冒泡排序（bubble_sort）16（1）基本原理：在每一趟冒泡排序中，依次比较相邻的两个关键字大小，若为反序咋交换。经过一趟起泡后，关键词大的必须移到最后。按照这种方式进行第一趟在

7、序列（I[0]~I[n-1]）中从前往后进行两个相邻元素的比较，若后者小，则交换，比较n-1次；第一趟排序结束，最大元素被交换到I[n-1]中，下一趟只需在子序列（I[0]~I[n-2]）中进行；如果在某一趟排序中未交换元素，则不再进行下一趟排序。将被排序的记录数组J[1…n]垂直排列，每个记录J[i]看作是重量为J[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止，最后可完成。（2）时间复杂度