实验报告五_2完整版.doc

宁波大学 科学技术 学院 数据结构 实验报告 实验名称 排序算法比较 实验者 08信计 肖勤伟 一 实验名称 排序算法比较分析 二 实验目的 1． 掌握各种排序的基本思想。 2． 掌握各种排序方法的算法实现。 3． 掌握各种排序方法的优劣分析及花费的时间的计算。 4． 掌握各种排序方法所适应的不同场合。 三 实验内容 利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间 四 实验步骤： 1需求分析 2算法概要 一、直接插入排序 ：instertionSort(a) 直接插入排序算法分析： 故,时间复杂度为O(n2)。 (4) 只需少量中间变量作为辅助空间。 (5) 算法是稳定的。 二、选择排序：selectionSort(b) 选择排序算法分析： (1)比较次数，在任何情况下,均为 (2)交换记录的次数 在最好情况下,原n个记录递增有序：不移动记录。 在最坏情况下共交换记录n-1对,移动记录数3(n-1)次。 故,时间复杂度为O(n2)。 (3)只需少量中间变量作为辅助空间。 (4)算法是不稳定的。 三、冒泡排序：bubbleSort(c) 冒泡排序算法分析： (1)最好情况, 待排序的文件已是有序文件: 只需要进行1趟排序, 共计比较关键字的次数为n－1 不交换记录。 (2)最坏情况, 要经过n-1趟排序， 所需总的比较关键字的次数为 (n-1)+(n-2)+...+1＝n(n-1)/2 交换记录的次数最多为 (n-1)+(n-2)+...+1＝n(n-1)/2 移动记录次数最多为 3n(n-1)/2 。 (3)只需要少量中间变量作为辅助空间。 算法是稳定的。 四、快序排序：QSort(d) 快速排序算法分析： (1)就平均速度而言， 快速排序是已知内部排序方法中最好的一种排序方法, 其时间复杂度为 O(nlog(n))。 (2)在最坏情况下， 快速排序所需的比较次数和冒泡排序的比较次数相同, 其时间复杂度为 O(n2)。 (3)快速排序需要一个栈作辅助空间，用来实现递归处理左、右子文件。 在最坏情况下,递归深度为n， 所需栈的空间大小为 O(n)。 (4)快速排序是不稳定的。 五、归并排序：MSort(e) 归并排序算法分析： (1)对n个记录的文件进行归并排序,共需 log2n? 趟, (2)每趟所需比较关键字的次数不超过n, 共比较 O(nlog2n) 次。 (3)每趟移动n个记录, 共移动记录 O(nlog2n) 个 (4)归并排序需要一个大小为n的辅助空间 y[1..n]。 (5)归并排序是稳定的。 六、堆排序：HeapSort(f) 堆排序算法分析： (1)堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成， 它们均是通过调用Heapify实现的。 (2)堆排序的最坏时间复杂度为 O(nlgn)。 (3)堆排序的平均性能较接近于最坏性能。 　 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 (4)堆排序是就地排序，辅助空间为 O(1)。 (5)它是不稳定的排序方法 3抽象数据操作 直接插入排序 ：instertionSort(a) 选择排序： selectionsort（b） 冒泡排序：bubbleSort(c) 快序排序：QSort(d) 归并排序：MSort(e) 堆排序：HeapSort(f) 4详细设计（源代码） package sort; import java.util.Date; import java.util.Random; public class Sort { public final static int size=3000; static int cx=0; static int[] a=new int[size]; static int[] b=new int[size]; static int[] c=new int[size]; static int[] d=new int[size]; static int[] e=new int[size]; static int[] f=new int[size]; p