实习四 内部排序算法的性能测试

1.需求分析：

【问题描述】：教材中，每种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，取得实际计算结果。 【基本要求】：

（1）对以下6种常用的内部排序算法进行比较：冒泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。

（2）待排序表的表长不小于100，其中的数据要用伪随机数产生程序产生，至少用要用5组不同的输入数据作比较，比较的指标为关键字的比较次数和记录的移动次数。 （3）最后要对结果进行分析，包括对各数组得出结果波动大小的解释。 【开发环境】： 系统：windows7 编程软件：VC++6.0

2.设计：

(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。

当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。

(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜； (3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。

时间的估算：

排序方法 直 接 简单选择 冒 泡 堆 排 序 归 并 快 速

平均时间性能 O(n2) O(n2) O(n2) O(nlog2 n) O(nlog2 n) O(nlog2 n) 最好时间性能 O(n) O(n) O(n) O(nlog2 n) O(nlog2 n) O(nlog2 n) 最坏时间性能 O(n2) O(n2) O(n2) O(nlog2 n) O(nlog2 n) O(nlog2 n) 具体思想

结构体定义：

typedef int KeyType ; typedef struct {

KeyType key; }DataType; typedef struct {

int compare;//比较次数 int move;//移动次数

//定义及初始化成员变量 }Perf;

主函数： void main()

{

int i,j,m,n,k; n = size/2;

int D[7];//shellsort的增量.lb100取上整时为7 for(m=0;n>=1;m++) {

D[m] = n; n = n/2; }

Perf per;

DataType a[size-1]; DataType b[size-1]; DataType c[size-1]; DataType d[size-1]; DataType e[size-1]; DataType f[size-1];

srand( (unsigned)time( NULL ) );//设置随机数种子 printf(\你想测试数据的组数:\

scanf(\表示有多少组测试数据 for(j=0;j

for(k=0;k

a[k].key = rand();//随机输入size个数值 b[k].key = a[k].key; c[k].key = a[k].key; d[k].key = a[k].key; e[k].key = a[k].key; f[k].key = a[k].key; }

per = BubbleSort(a,size);

printf(\第%d组冒泡法排序时的移动次数和比较次数：\\n\ printf(\ %d\\n\ per = InsertSort(b,size);

printf(\第%d组直接插入法排序时的移动次数和比较次数：\\n\ printf(\ %d\\n\ per = SelectSort(c,size);

printf(\第%d组简单选择法排序时的移动次数和比较次数：\\n\ printf(\ %d\\n\ per = visit(d,0,size-1);

printf(\第%d组快速排序法排序时的移动次数和比较次数：\\n\ printf(\ %d\\n\ per = ShellSort(e,size,D,m);

printf(\第%d组希尔排序时的移动次数和比较次数：\\n\ printf(\ %d\\n\ per = HeapSort(f,size);

printf(\第%d组堆排序时的移动次数和比较次数：\\n\ printf(\ %d\\n\ printf(\ }

printf(\} 模块： mainBubbleSortInsertSortSelectSortQuickSortShellSortHeapSortComparemove 3.调试分析 首先是srand( (unsigned)time( NULL ) )//设置随机数种子,然后通过rand()函数随机输入size（size为100）个数值，开始时不了解rand()函数没有包含其头文件\而导致出错，然后就是将rand()函数产生的随机值放到一个数组中，不同的排序都用该数组存储的rand()函数产生的随机值，发现调用时出现错误，而是rand()函数产生的随机值放到一个数组中，然后，在定义5个数组，分别存储第一个数组的中的数据，例如 a[k].key = rand(); b[k].key = a[k].key;c[k].key = a[k].key; d[k].key = a[k].key;e[k].key = a[k].key;f[k].key = a[k].key;不同的排序算法用不同的数组存储的数据，这样才不出错。各个排序的算法书上都已经给出，但要认真理解每个排序算法，敲代码时容易出现敲错的一些小问题。