八种排序算法内部排序法实验报告

《八种排序算法内部排序法实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告内部排序算法比较院系:信息科学与工程学院专业:2015物理学姓名:朱晓真学号:15020011050实验报告一．实验名称：内部排序算法比较二．课程设计目的及要求1.课程设计目的：课本中各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。通过随机数据比较各算法的关键比较次数和关键字移动次数，同时给出实际排序时间，以取得直观感受。2.实验要求：①对以下八种常用内部排序算法进行比较：直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序。②

2、待排序表的表长不小于10万；其中的数据要用伪随机数程序产生；至少要5组不同的输入数据做比较；比较的指标为有关键字参加的比较次数、关键字的移动次数（关键字交换记为3次移动）、排序时间。③最后对结果做简单分析，包括对各组数据得出结果波动大小的解释。④提供友好的用户交互界面。三．课程设计思想以及具体实现1.课程设计思想:①分别用8个子函数来进行8种排序：直接插入排序：voidInsertSort(SqList&L1,SqList&L)希尔排序：voidShellsort(SqList&L1,SqList

3、&L)冒泡排序：voidbubblesort(SqList&L1,SqList&L)快速排序：voidQuickSort(SqList&L1,SqList&L)简单选择排序：voidSelectSort(SqList&L1,SqList&L)堆排序：voidHeapSort(SqList&L1,SqList&L)归并排序：voidMergeSort(SqList&L1,SqList&L)基数排序：voidRadixsort(SqList&L1,SqList&L)②每个子函数中设置com来表示比较次

4、数，关键字每比较1次，com+1。设置mov来表示关键字移动次数，普通移动时mov+1，关键字交换时mov+3。③100000个数据（排序表）由伪随机数程序产生（伪随机数的产生与时间相关）④引入#include头文件，定义：clock_tstart_t,end_t;start_t记录起始时间。end_t记录结束时间。⑤构造元素链表SqList，记录产生的随机数。⑥定义全局变量t0~t7，计算start_t和end_t的差值，求出排序时间。⑦使用voidaddlist(SqList&

5、L,intj)产生随机数，j为随机数随机产生的种子。产生随机数的关键代码：L.elem[i].key=rand()+(j*rand())%10;四．实验结果操作界面：选择排序：数据分析：①比较次数：选择排序的几组比较次数均不变，平均比较次数与各组数据相同，这与选择排序的比较次数永远为n(n-1)/2。所以验证了选择排序的比较次数不发生波动，在比较次数方面具备稳定性；②移动次数：选择排序的几组移动次数发生了变化，但发生变化的数量级仅为10位数，因此在移动次数方面存在轻微波动性。同样验证了选择排序的移

6、动次数存在有最好/最坏次数的波动，因此选择排序的移动次数存在轻微波动性。③比较时间：选择排序的几组比较时间之间对比发现，从几组比较时间和平均比较时间数据可以看出，选择排序的比较时间相对于其数量级来说，每次排序发生着极大的波动。验证了选择排序的比较时间存在最好/最坏情况，因此选择排序的比较次数存在着波动性。冒泡排序：数据分析：①比较次数：分析冒泡排序的几组比较次数和平均比较次数数据得出，冒泡排序的比较次数均不发生变化，因此可验证冒泡排序的比较次数具备稳定性。②移动次数：分析冒泡排序的几组移动次数和平

7、均移动次数数据得出，几组移动次数与平均移动次数存在的差异不大，证明冒泡排序的移动次数存在着稳定性，因此验证了冒泡排序的移动次数存在有最好/最坏情况，因此移动次数的数据存在稳定性；③比较时间：分析冒泡排序的几组比较时间和平均比较时间数据得出，比较时间的平均均差为0.2，因此在数据中波动性不大。希尔排序：数据分析：①比较次数：几组比较次数与平均比较次数可得出，这几组数据与平均比较次数相差较大，存在波动性；另外平均均差为“1841813.6”，也可以验证希尔排序比较次数具有波动性。因此可以验证希尔排序的

8、比较次数具有波动性。②移动次数：几组移动次数与平均移动次数可得，希尔排序的几组移动次数存在轻微波动，但波动性不大。③比较时间：几组比较时间的平均均差为“65”毫秒，相对来说具备轻微波动性。直插排序：数据分析：①比较次数：由于直插排序的几组比较次数数量级较大，单方面从单次均差观察很难得出结论，因此对几组比较次数的均差进行求均值，得出平均均差为“0”，因此直插排序的比较次数具备稳定性。②移动次数：由于直插排序的几组移动次数数量级较大，单方面从单次均差观察很难得出结论，因此对几组移动次数