实 验（实训）报 告
项 目 名 称 各种排序算法时间复杂度测试 所属课程名称 数据结构 项 目 类 型 综合实验 实验(实训)日期 2012年11月21日—30日
班 级 学 号 姓 名 指导教师 万贤美
浙江财经学院教务处制
第7章实验 排序算法时间效率测试
实验类型：综合型
实验目的：
1. 理解排序算法的基本思路； 2. 掌握排序算法的设计与实现；
3. 学会运用相关函数和工具测试算法时间耗费。
实验要求：
1. 认真阅读课本关于各种排序算法的思路，掌握分析排序算法的图示方法；
2. 设计算法测试程序，用六种排序算法分别对随机产生的数据进行排序，记录时间耗费； 3. 对实验结果进行处理与分析。
实验任务： 1、 以学生本人的学号为工程名，建立一个win32 console application工程。 2、 3、 4、
设计直接插入排序、冒泡排序、快速排序、简单选择排序算法，每个算法用一个函数实现；（选做：二分法插入排序）
对于两种数据规模n=10000和n=100000，随机产生十组整数，对于每一组数据，分别运用各种排序算法进行排序，记录其时间耗费（时间为秒）； 实验报告要求：
（1） 把完成本实验的程序粘贴在后面； （2） 根据上述记录数据进行计算与分析
(a) 对于每一种算法，统计排序过程中比较和移动的次数，并通过两种不同数据规模的
时间耗费，验证其时间复杂度，要求用表格、文字进行说明。
(b) 根据（1）的计算结果，从算法时间效率、程序复杂性三个方面，对各种排序算法进
行比较，要求设计合适的表格进行数据比较，并对分析结果进行文字说明。
测试程序说明：（1）使用该排序算法，每一组数据排序时间约需要10秒以上，请耐心等待。（2）测试程序运用了C++提供的机器时钟读数函数clock()，该函数返回机器钟当前的振动次数。
#include
#define N 100000 void main() { int *a=new int[N]; //堆分配大规模内存
int *b=new int[N]; //堆分配大规模内存
clock_t start, finish; //记录排序前后的时间。clock_t是“机器钟”类型
2
double duration; //排序花费的时间
srand( (unsigned)time( NULL )+ 学号 ); //产生随机数种子
for (int k=1; k<=10; k++) { //产生十组随机数 for (int i=0; i start = clock(); //记录排序开始时的机器时间 //以下调用第一个排序算法，对N个数排序 //…… finish = clock(); //记录排序结束时的机器时间 duration = (double)(finish - start); //单位为毫秒 cout<<\ //输出排序花费的时间 //以下调用第二个排序算法，对N个数排序 // 把数组b中的数据转入至数组a for (int i=0; i start = clock(); //记录排序开始时的机器时间 // 调用排序算法…… finish = clock(); //记录排序结束时的机器时间 duration = (double)(finish - start); //单位为毫秒 //输出排序花费的时间 cout<<\ //完成其它排序算法的测试 ……… } delete []a; delete []b; } 实验报告写在后页 3 比较次数，移动次数程序 int CompareNum1; int MoveNum1; //直接插入排序，数组data用于存放待排序元素，n为待排序元素个数 template void InsertSort(ElemType data[],int n) { CompareNum1=0; MoveNum1=0; ElemType tmp; int i,j; for(i=1;i int CompareNum2; int MoveNum2; //冒泡排序 template 4 void BubbleSort(ElemType data[],int n) { CompareNum2=0; MoveNum2=0; int lastSwapIndex=n-1; int i,j; for (i = lastSwapIndex; i > 0;i = lastSwapIndex) { lastSwapIndex = 0; for (j = 0; j < i; j++){ if (data[j] > data[j + 1]){ Swap( data[j],data[j + 1]); lastSwapIndex = j; MoveNum2+= 3; } CompareNum2++; } } } //交换函数 template T c=a; a=b; b=c; } int CompareNum3; int MoveNum3; //快速排序 template int Partition(ElemType data[] , int low , int high) { CompareNum3=0; MoveNum3=0; ElemType pivot = data[low]; while (low < high){ while (low < high && data[high] >= pivot){ 5