数据结构预算法之排序算法比较

1、数据结构与算法课程数据结构与算法课程综合训练实验报告综合训练实验报告第 1 次姓名姓名魏豪班级班级软件 62学号学号2161601038电话电日期日期2017-10-18一、实验题目一、实验题目任务 1完成直接插入排序、简单选择排序、冒泡排序、快速排序和归并排序的实现；要求：不能使用你所使用的编程语言内置的排序算法；排序算法的实现只能使用最基本的交换、比较、循环等操作；每个排序算法都尽可能使用课堂上所讲授的步骤， 不要对任何排序算法进行额外的优化。任务 2完成对每一个排序算法在输入规模为：100、200、300、10000 的排序时间统计。要求：在同等规模的数据量下，

2、需要统计正序序列和逆序序列两种序列的排序时间；将所有记录的排序时间按照如下分类方式进行图示化，需要完成如下的 7 张图：图 1-图 5：每一个图对应一个排序算法，相应的图中记录该排序算法对正序序列和逆序数据序列的时间（x 轴代表数据规模、y 轴代表运行时间，以下同） ；图 6：用来将 5 个排序算法在正序数据序列下的运行时间图示化；图 7：用来将 5 个排序算法在逆序数据序列下的运行时间图示化；在每张图的下面用简短的语句描述时间变化趋势的原因。任务 3完成对每一个排序算法在输入规模为：100、200、300、10000 的随机数据序列的排序时间统计。要求：切记，每个排序算法在同样数据规模的随机

3、序列要保持一致；记录 5 个排序算法在相同规模下的排序时间，并形成图 8；图 8：用来将 5 个排序算法在随机数据序列下的运行时间图示化；二、实验内容二、实验内容任务一：任务一：a)直接插入排序：public static void sort(int array) for(int i = 1; i 0) &(arrayj arrayj-1); j-) int temp = arrayj;arrayj = arrayj-1;arrayj-1 = temp;b)简单选择排序：public static void simpleSelectMethod(int array)/lowIndex用

4、于记录i+1到args.length-1这个区间的最小值的下标（i会递增），i表示要交换的位置。for(int i = 0; i array.length-1; i+) int lowIndex = i;for(int j = i + 1; j array.length; j+)if(arrayj arraylowIndex)lowIndex = j;if(lowIndex != i) int temp = arraylowIndex;arraylowIndex = arrayi;arrayi = temp;c)冒泡排序：public static void BubbleSort(int ar

5、ray) for(int i = 0; i i; j-) if(arrayj 1) qsort(array, i, k - 1);if(j - k) 1) qsort(array, k+1, j);public static void swap(int array, int a, int b) int temp = arraya;arraya = arrayb;arrayb = temp;public static int partition(int array, int l, int r, int pivot) do while(array+l pivot);swap(array, l, r

6、);while(l r);swap(array, l, r);return l;e)归并排序：public static void mergeSort(int a, int left, int right) if (left right) int center = (left + right) / 2;mergeSort(a, left, center);mergeSort(a, center + 1, right);merge(a, left, center + 1, right);public static void merge(int a,int leftPos, int rightPo

7、s, int rightEnd) int temp = new intrightEnd - leftPos + 1;int n = leftPos;int m = rightPos;int i = 0;while (n rightPos & m = rightEnd ) if (an am) tempi+ = an+; else tempi+ = am+;while (n rightPos) tempi+ = an+;while (m = rightEnd) tempi+ = am+;for(int j = 0; j temp.length;j+) aj + leftPos = tem

8、pj;任务二：任务二：(a)图 1 直接插入排序在正逆序数据序列下的运行时间直接插入排序算法在正序序列情况下运行时间为 O(N),因为内层 for 循环的检测总是立即判定不成立而终止； 在逆序序列情况下进行 n(n-1)/2 次比较和交换操作， 速度慢。(b)图 2 简单选择排序在正逆序数据序列下的运行时间简单选择排序算法实质上就是冒泡排序， 只是记住最小元素的位置并用最后一次交换使他到位，而不是不断地交换相邻记录。在正序序列情况下只进行 n(n-1)/2 - 1 次比较操作，速度较快；在最坏情况即逆序序列情况下进行全部的 n(n-1)/2 次比较和 n 次交换操作，故速度慢。(c)图 3 冒

9、泡排序在正逆序数据序列下的运行时间冒泡排序算法在最好情况即正序序列情况下进行 n2/2 次比较操作，速度较快；在最坏情况即逆序序列情况下进行全部的 n2/2 次比较和交换操作，速度慢。(d)图 4 快速排序在正逆序数据序列下的运行时间快速排序实质上是递归的。快速排序算法在正序序列情况下的时间复杂度为 O(nlogn)；在逆序序列情况下的时间复杂度为 O(nlogn)，两种情况下速度相差不大。因为递归和轴值的选择使排序时间不具有较强的规律性。(e)图 5 归并在正逆序数据序列下的运行时间归并排序也是递归程序，当被排序元素数目为 n 时，递归的深度为 log n，在所有log n 层递归中，每一层

10、都需要(n)的时间开销，因此总的时间代价为 O(n log n)，这个时间代价并不依赖于元素的相对顺序，故正逆序时间相似。（f）图 6 五种排序算法在正序数据序列下的运行时间由上表可以看出， 在正序序列情况下， 五种排序算法的运行时间快慢顺序由慢到快依次为：冒泡排序、简单选择排序、归并排序、快速排序、直接插入排序。简单选择排序和冒泡排序进行 n2次比较操作，用时最长。时间复杂度 O(n2)。归并排序和快速排序进行 nlog2n 次比较和交换操作，用时较短。时间复杂度O(nlogn)。直接插入排序进行 n 次比较操作，用时最短。时间复杂度 O(n)。（g）图 7 五种排序算法在逆序数据序列下的运

11、行时间由上表可以看出， 在逆序序列情况下， 五种排序算法的运行时间快慢顺序由慢到快依次为：简单选择排序、冒泡排序、直接插入排序、归并排序、快速排序。直接插入排序、冒泡排序、简单选择排序时间复杂度 O(n2)，用时较长。归并排序和快速排序进行 nlog2n 次比较和交换操作， 用时短。 时间复杂度 O(nlogn)。任务三：任务三：生成随机序列数据方法：for(int a = 100; a = 10000; a += 100) int args2 = new inta;for(int i = 0; i a; i+) args2i = new Random().nextInt(10000) + 1;图 8 五种排序算法在随机数据序列下的运行时间由上表可以看出， 在随机数据序列情况下， 五种排序算法的运行时间快慢顺序由慢到快依次为：冒泡排序、简单选择排序、直接插入排序、归并排序、快速排序。冒泡排序平均进行 n2次比较和 n2/2 次交换操作，用时长。时间复杂度 O(n2)。简单选择排序平均进行 n2次比较和 n 次交换操作，用时较长。时间复杂度 O(n2)。直接插入排序平均进行n2/2次比较和n2/2次交换操作， 用时较长。 时间复杂度O(n2)。归并排序和快速排序平均进行 nlog2n 次比较和交换操作，用时短。时间复杂度O(nlogn)。三、实验总结三、实验总结