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

实 验 报 告

（ 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];