浙江财经学院数据结构排序实验

实 验（实训）报 告

项 目 名 称 各种排序算法时间复杂度测试 所属课程名称 数据结构 项 目 类 型 综合实验 实验(实训)日期 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 #include #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;idata[i-1]) { CompareNum1++; continue; } tmp=data[i]; //保存待插入的元素 data[i]=data[i-1]; MoveNum1+=2; for(j=i-1;j>0&&data[j-1]>tmp;j--) { data[j]=data[j-1]; //元素后移 CompareNum1++; MoveNum1++; } data[j]=tmp; MoveNum1++; } }

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 void Swap(T &a,T &b) {

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

high--; CompareNum3++; } CompareNum3++;

data[low] = data[high]; while (low < high && pivot >= data[low]){ low++; CompareNum3++; } CompareNum3++;

data[high] = data[low]; MoveNum3+= 2; }

data[low] = pivot;

MoveNum3 += 2;

return low; }

template

void QuickSort(ElemType data[], int begin, int end) {

if (begin >= end) return;

int pivot = Partition(data , begin , end); QuickSort(data , begin , pivot - 1);

QuickSort(data , pivot + 1, end); }

template

void QuickSort(ElemType data[], int n) {

if (n < 2) return;

CompareNum3 = MoveNum3 = 0; QuickSort(data, 0, n-1); }

6

int CompareNum4;

int MoveNum4;// 简单选择排序 template

void SelectionSort(ElemType data[], int n) {

CompareNum4=0; MoveNum4=0; int i, j, min;

for (i = 0; i < n; i++){ min = i;

for (j = i + 1; j < n; j++){ if ( data[j] < data[min]) min = j; CompareNum4++; }

Swap(data[i],data[min]); MoveNum4 += 3; } }

#include #include \#include \#include \#include %using namespace std;

void main() { // int

CompareNum1,MoveNum1,CompareNum2,MoveNum2,CompareNum3,MoveNum3,CompareNum4,MoveNum4;

int a[10]={1,9,3,7,25,48,21,5,8,10}; int n=10,i;

cout<<\ for(i=0;i

7

InsertSort(a,n); BubbleSort(a,n); QuickSort(a,n); SelectionSort(a,n);

cout<<\ for(i=0;i cout<<\直接插入排序比较次数=\移动次数=\

cout<<\冒泡排序比较次数=\移动次数=\ cout<<\快速排序比较次数=\移动次数=\ cout<<\简单选择排序比较次数=\移动次数=\}

时间复杂度比较程序 //InsretSort.h //直接插入排序

template

void InsertSort(ElemType data[],int n) {

ElemType tmp; int i,j;

for(i=1;idata[i-1]) { continue; } tmp=data[i]; //保存待插入的元素 data[i]=data[i-1]; for(j=i-1;j>0&&data[j-1]>tmp;j--) {

8

data[j]=data[j-1]; //元素后移 } data[j]=tmp; } }

//BubbleSort.h //冒泡排序

template

void BubbleSort(ElemType data[],int n) {

int lastSwapIndex=n-1; int i,j;

for( i=lastSwapIndex;i>0;i=lastSwapIndex ) { lastSwapIndex=0; for(j=0;jdata[j+1]) { Swap(data[j],data[j+1]); lastSwapIndex=j; } } } }

//交换函数

template void Swap(T &a,T &b) {

T c=a; a=b; b=c; }

9

// Partition.h //快速排序

template

int Partition(ElemType data[] , int low , int high) {

ElemType pivot = data[low]; while (low < high){

while (low < high && data[high] >= pivot) high--;

data[low] = data[high];

while (low < high && pivot >= data[low]) low++;

data[high] = data[low]; }

data[low] = pivot; return low; }

template

void QuickSort(ElemType data[], int begin, int end) {

if (begin >= end) return;

int pivot = Partition(data , begin , end); QuickSort(data , begin , pivot - 1);

QuickSort(data , pivot + 1, end); }

template

void QuickSort(ElemType data[], int n) {

if (n < 2) return;

QuickSort(data, 0, n-1); }

// SelectionSort.h // 简单选择排序

10

template

void SelectionSort(ElemType data[], int n) {

int i, j, min;

for (i = 0; i < n; i++){ min = i;

for (j = i + 1; j < n; j++){ if ( data[j] < data[min]) min = j; }

Swap(data[i],data[min]); } }

//Main.cpp

#include #include #include #include \#include \#include \#include \

#define N 100000000 void main() {

int n=100000;

int *a=new int[N]; //堆分配大规模内存 int *b=new int[N]; //堆分配大规模内存

clock_t zjcrstart, zjcrfinish,mpstart, mpfinish,ksstart, ksfinish,jdxzstart,jdxzfinish; 记录排序前后的时间。clock_t是\机器钟\类型

double zjcrduration,mpduration,ksduration,jdxzduration; //排序花费的时间

//产生随机数种子

srand( (unsigned)time( NULL )+ 110104200145 ); for (int k=1; k<=10; k++) { //产生十组随机数 for (int i=0; i

11

// { b[i]=a[i]=rand(); //产生N个随机数, a数组用于排序，b数组用于保留原始数据 } zjcrstart = clock(); //记录排序开始时的机器时间 //以下调用第一个排序算法，对N个数排序 cout<<\ for(int j=0;j

12

a[w]=b[w]; } ksstart = clock(); //记录排序开始时的机器时间 // 调用排序算法…… QuickSort(a,n); ksfinish = clock(); //记录排序结束时的机器时间 ksduration = (double)(ksfinish - ksstart); //单位为毫秒 cout<<\快速排序花费的时间 = \//输出排序花费的时间 //简单选择排序 for (int e=0; e

以a[10]={1,9,3,7,25,48,21,5,8,10}为例 直接插入排序 冒泡排序 快速排序 简单选择排序 比较次数 13 9 3 45 移动次数 28 0 4 30

13

经过比较发现，当规模不断增加时，各种算法之间的差别是很大的。这六种算法中，快速排序比较和移动的次数是最少的,也是最快的一种排序方法。直接选择排序虽然交换次数很少，但比较次数较多.

以n=100000为例：

14

当数据规模很大时，冒泡排序花费的时间最多，快速排序花费的最少。

15

本文来源：https://www.bwwdw.com/article/8xo5.html