数据结构试验报告 - 各种内排序算法的实现及性能比较

实 验 报 告

（ 2010 / 2011 学年 第 2 学期）?

???

课程名称 数据结构——使用C++语言描述 实验名称 各种内排序算法的实现及性能比较

实验时间 2011 年 5 月 27 日

指导单位 计算机科学与技术系 指导教师

学生姓名 学院(系)

班级学号 专 业

实验名称 实验类型

设计 各种内排序算法的实现及性能比较 指导老师 实验学时 4 实验时间 2011.5.27 一．实验目的和要求

内容：

验证教材的各种内排序算法。分析各种排序算法的时间复杂度。 要求：

使用随机数产生器产生大数据集合，运行上述各种排序算法，使用系统时钟测量各算法所需的实际时间，并进行比较。

二．实验环境（实验设备）

Visual C++6.0

三．实验原理及内容

//selectsort.h

#include //简单选择排序 template

void SelectSort(T A[], int n) {

int small;

for (int i=0; iInsertsort.h

#include //直接插入排序 template

void InsertSort(T A[], int n) {

for(int i=1; i

int j=i; T temp=A[i]; while(j>0&&temp

Bubblesort.h

#include template

void BubbleSort(T A[], int n) {

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

while(i>0){ last=0; for(j=0;jQuicksort.h

#include //改进的快速排序 template void quick(T A[],int n) {

int *a; //用数组保存待排序的子序列的上、下界 int top=0,right,left,j; //left和right为待排序 a=new int[n];

if(a==NULL) return; a[top++]=0;

a[top++]=n-1; //以初始序列为待排序序列开始改进的快速排序 //lc

for(j=0;a[j]!=NULL;j++) //循环到数组元素为空 { left=a[j++]; right=a[j]; //每次按序从数组中取出两个元素作为待排序序列的上、下界 if(left>right)

Swap(left,right); //如果下界大于上界，交换上、下界 if(right-left<15) InsertSortExt(A,left,right); //若元素较少调用插入排序 else { a[top++]=left; a[top++]=QuickSort(A,left,right)-1; a[top++]=a[top-2]+2; a[top++]=right; //否则将低、高端序列上、下界依次保存到数组中 } } }

template

int QuickSort(T A[],int left,int right) //用于改进的快速排序的原始快速排序方法 {

int i,j;

if(left

return 0; }

template

void InsertSortExt(T A[],int left,int right)//用于快速排序的直接插入排序方法 {

for(int i=left+1; i0 && temp

Mergesort.h

#include //两路合并的C++程序

template

void Merge(T A[],int i1,int j1,int i2,int j2)

{ // i1,j1是子序列1的下、上界，i1,j2是子序列2的下、上界

T *Temp=new T[j2-i1+1]; //分配能存放两个子序列的临时数组 int i=i1,j=i2,k=0; //i,j是两个子序列的游动指针，k是Temp的游动指针

while(i<=j1&&j<=j2) if(A[i]<=A[j])Temp[k++]=A[i++]; else Temp[k++]=A[j++]; while(i<=j1)Temp[k++]=A[i++]; while(j<=j2)Temp[k++]=A[j++]; for(i=0;i

delete [] Temp; }

//合并排序的C++程序 template

void MergeSort(T A[], int n) {

int i1,j1,i2,j2; //i1,j1是子序列1的下、上界，i2,j2是子序列2的下、上界 int size=1; //子序列中元素个数，初始化为1。 while(sizen-1) j2=n-1; else j2=i2+size-1; Merge(A,i1,j1,i2,j2); i1=j2+1; } size*=2; } }

Heapsort.h

#include //AdjustDown函数 template

void AdjustDown(T A[], int r, int j) {

int child=2*r+1; T temp=A[r];

while(child<=j){ if((child

A[(child-1)/2]=temp; }

//堆排序的C++程序 template

void HeapSort(T A[], int n) {

for(int i=(n-2)/2; i>-1; i--) AdjustDown(A,i,n-1); for(i=n-1; i>0; i--){ Swap(A[0],A[i]); AdjustDown(A,0,i-1); } }

Meau.h

#include #include #include #include

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

#define SIZE 400 #define TIMES 1000 template class Menu {

public:

void printmenu();

void selectsort();//简单选择排序 void insertSort();//直接插入排序 void bubbleSort();//冒泡排序 void quickSort();//快速排序

void mergeSort();//两路合并排序

//构造最大堆 void heapSort();//堆排序 void childmenu();//子菜单1 void childmenu2();//子菜单2 void switcha(); private:

int a,b,c; };

template

void Menu::printmenu() { cout<<\ cout<<\ 内排序测试系统 \

cout<<\ cout<<\简单选择排序\ cout<<\直接插入排序\ cout<<\冒泡排序\ cout<<\快速排序\ cout<<\两路合并排序\ cout<<\堆排序\ cout<<\退出\ cout<<\：测试用的数组元素为\时间为重复运行\次的时间（包括了产生数据与析构的时间）\ this->switcha(); }

template

void Menu::childmenu() {

cout<<\ cout<<\最好情况\ cout<<\最坏情况\ cout<<\平均情况\ cout<<\返回主菜单\ cin>>b;

if(b==4)this->printmenu(); }

template

void Menu::childmenu2() {

cout<<\ cout<<\原始算法\ cout<<\改进算法\ cout<<\返回主菜单\

cin>>c;

if(c==3)this->printmenu(); }

template

void Menu::switcha() {

//cout<<\ cin>>a; switch(a) {

case 1:this->selectsort();break;//ok case 2:this->insertSort();break;//ok case 3:this->bubbleSort();break;//ok case 4:this->quickSort();break;//ok case 5:this->mergeSort();break;//ok case 6:this->heapSort();break;//ok case 7:exit(1);break;

default:cout<<\ } };

template

void printout(T A[],int n)//打印数组，测试时用 {

for(int i=0;itemplate

T *producedate(int x)//产生顺序，逆序，随机的数组 {

int i;

T *A=new T[SIZE]; switch(x) {

case 1: for(i=0;i

case 2:for(i=SIZE;i>0;i--)A[i-1]=SIZE-i;return A;//逆序 break;

case 3:srand(time(NULL)); for(i=0;i

} }

template

void Swap(T &a,T &b)//交换2个元素 {

T temp=a; a=b; b=temp; }

template

void Menu::bubbleSort() {

cout<<\冒泡排序\ this->childmenu(); T *A;

double duration; clock_t start,finish; start=clock();

cout<<\

for(int i=0;i(b); BubbleSort(A,SIZE); delete []A; }

finish=clock();

duration=(double)(finish-start)/CLOCKS_PER_SEC; //printout(A,SIZE);

cout<<\用时： \ system(\ //delete []A;

this->bubbleSort(); }/*ok*/

template

void Menu::heapSort() {

cout<<\堆排序\

cout<<\直接用随机数据测试\ T *A;

double duration; clock_t start,finish; start=clock();

cout<<\

for(int i=0;i(3); HeapSort(A,SIZE); delete []A; }

finish=clock();

duration=(double)(finish-start)/CLOCKS_PER_SEC;

cout<<\用时： \ system(\

this->printmenu(); }

template

void Menu::insertSort() {

cout<<\直接插入排序\ this->childmenu(); T *A;

double duration;

//A=producedate(b);

//if(A==NULL){cout<<\ //printout(A,SIZE); clock_t start,finish; start=clock();

cout<<\

for(int i=0;i(b); InsertSort(A,SIZE); delete []A; }

finish=clock();

duration=(double)(finish-start)/CLOCKS_PER_SEC; //printout(A,SIZE);

cout<<\用时： \ system(\ //delete []A;

this->insertSort(); }

template

void Menu::mergeSort() {

//this->childmenu();

cout<<\合并排序\

cout<<\直接用随机数据测试\ T *A;

double duration; clock_t start,finish; start=clock();

cout<<\

for(int i=0;i(3); MergeSort(A,SIZE); delete []A; }

finish=clock();

duration=(double)(finish-start)/CLOCKS_PER_SEC; //printout(A,SIZE);

cout<<\用时： \ system(\ //delete []A;

this->printmenu(); }/*ok*/

template

void Menu::quickSort() {

this->childmenu2(); T *A;

double duration; clock_t start,finish; if(c==1) { cout<<\原始快速排序\ cout<<\直接用随机数据测试\ start=clock(); cout<<\ for(int i=0;i(3); QuickSort2(A,SIZE); delete []A; } finish=clock(); duration=(double)(finish-start)/CLOCKS_PER_SEC;

cout<<\用时： \ system(\ }

else if(c==2) {

cout<<\改进的快速排序\ cout<<\直接用随机数据测试\ /*A=producedate(3); printout(A,SIZE); quick(A,SIZE); printout(A,SIZE); delete []A;

this->printmenu(); */

//T *A;

start=clock();

cout<<\

for(int i=0;i(3); quick(A,SIZE); delete []A; }

finish=clock();

duration=(double)(finish-start)/CLOCKS_PER_SEC;

cout<<\用时： \ system(\

this->quickSort(); }

else{cout<<\}

template

void Menu::selectsort() {

//this->childmenu();

cout<<\简单选择排序\

cout<<\直接用随机数据测试\ T *A;

double duration; clock_t start,finish; start=clock();

cout<<\

for(int i=0;i(3); SelectSort(A,SIZE); delete []A; }

finish=clock();

duration=(double)(finish-start)/CLOCKS_PER_SEC; //printout(A,SIZE);

cout<<\用时： \ system(\ //delete []A;

this->printmenu(); }

/*ok!*/

Mymain.cpp

#include \int main() {

Menu MenuObj; MenuObj.printmenu();

cout<<\ return 0; } /*ok

-------------------------------------------------------- 内排序测试系统

--------------------------------------------------------

1.简单选择排序 2.直接插入排序 3.冒泡排序 4.快速排序

5.两路合并排序 6.堆排序 7.退出

PS：测试用的数组元素为400时间为重复运行1000次的时间（包括了产生数据与析构的时间） ok

1

简单选择排序

直接用随机数据测试 ok

用时： 0.593

请按任意键继续. . .

-------------------------------------------------------- 内排序测试系统

--------------------------------------------------------

1.简单选择排序 2.直接插入排序 3.冒泡排序 4.快速排序

5.两路合并排序 6.堆排序 7.退出

PS：测试用的数组元素为400时间为重复运行1000次的时间（包括了产生数据与析构的时间） ok 2

直接插入排序

-------------------------------------------------------- 1.最好情况 2.最坏情况 3.平均情况 4.返回主菜单 1 ok

用时： 0

请按任意键继续. . . 直接插入排序

-------------------------------------------------------- 1.最好情况 2.最坏情况 3.平均情况 4.返回主菜单 2 ok

用时： 0.703

请按任意键继续. . . 直接插入排序

--------------------------------------------------------

1.最好情况 2.最坏情况 3.平均情况 4.返回主菜单 3 ok

用时： 0.39

请按任意键继续. . . 直接插入排序

-------------------------------------------------------- 1.最好情况 2.最坏情况 3.平均情况 4.返回主菜单 4

-------------------------------------------------------- 内排序测试系统

--------------------------------------------------------

1.简单选择排序 2.直接插入排序 3.冒泡排序 4.快速排序

5.两路合并排序 6.堆排序 7.退出

PS：测试用的数组元素为400时间为重复运行1000次的时间（包括了产生数据与析构的时间） ok 3

冒泡排序

-------------------------------------------------------- 1.最好情况 2.最坏情况 3.平均情况 4.返回主菜单 1 ok

用时： 0.015

请按任意键继续. . . 冒泡排序

-------------------------------------------------------- 1.最好情况

2.最坏情况 3.平均情况 4.返回主菜单 2 ok

用时： 2.594

请按任意键继续. . . 冒泡排序

-------------------------------------------------------- 1.最好情况 2.最坏情况 3.平均情况 4.返回主菜单 3 ok

用时： 1.969

请按任意键继续. . . 冒泡排序

-------------------------------------------------------- 1.最好情况 2.最坏情况 3.平均情况 4.返回主菜单 4

-------------------------------------------------------- 内排序测试系统

--------------------------------------------------------

1.简单选择排序 2.直接插入排序 3.冒泡排序 4.快速排序

5.两路合并排序 6.堆排序 7.退出

PS：测试用的数组元素为400时间为重复运行1000次的时间（包括了产生数据与析构的时间） ok 4

-------------------------------------------------------- 1.原始算法 2.改进算法 3.返回主菜单

1

原始快速排序

直接用随机数据测试 ok

用时： 0.187

请按任意键继续. . .

-------------------------------------------------------- 1.原始算法 2.改进算法 3.返回主菜单 2

改进的快速排序 直接用随机数据测试 ok

用时： 0.172

请按任意键继续. . .

-------------------------------------------------------- 1.原始算法 2.改进算法 3.返回主菜单 3

-------------------------------------------------------- 内排序测试系统

--------------------------------------------------------

1.简单选择排序 2.直接插入排序 3.冒泡排序 4.快速排序

5.两路合并排序 6.堆排序 7.退出

PS：测试用的数组元素为400时间为重复运行1000次的时间（包括了产生数据与析构的时间） ok 5

合并排序

直接用随机数据测试 ok

用时： 0.454

请按任意键继续. . .

-------------------------------------------------------- 内排序测试系统

--------------------------------------------------------

1.简单选择排序 2.直接插入排序 3.冒泡排序 4.快速排序

5.两路合并排序 6.堆排序 7.退出

PS：测试用的数组元素为400时间为重复运行1000次的时间（包括了产生数据与析构的时间） ok 6

堆排序

直接用随机数据测试 ok

用时： 0.172

请按任意键继续. . .

-------------------------------------------------------- 内排序测试系统

--------------------------------------------------------

1.简单选择排序 2.直接插入排序 3.冒泡排序 4.快速排序

5.两路合并排序 6.堆排序 7.退出

PS：测试用的数组元素为400时间为重复运行1000次的时间（包括了产生数据与析构的时间） ok 7

Press any key to continue */

四．实验小结（包括问题解和解决方法、心得体会、意见与建议等）

通过本次实验对教材上的各种内排序算法进行了逐一验证。并通过分析各种排序算法的时间复杂度。对每种算法的效率有了进一步了解。

五．指导老师评语

成 绩 批阅人 日 期

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