数据结构课程设计实验报告

数据结构课程设计

题目： 内部排序算法的比较

姓名： 李吉倩

学号： 020332010046 系年级： 计算机科学与技术2010级 完成时间：2012.8-2012.9

1

数据结构课程设计 中国海洋大学

一、需求分析

实验报告

1.本程序对以下六种常用的内部排序进行实测比较：起泡排序、直接插入 排序、简单选择排序、快速排序、希尔排序、堆排序。

2.待排序表的元素的关键字为整数，雍正徐、逆序和随机数产生器产生的随机数做测试比较。比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。

3.程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”下，用户可由键盘输入产生随机数的种子，计算机终端显示各内部排序的比较参数。

4.最终对结果做出简单分析，包括对各组数据得出结果波动大小给予解释。 二、概要设计

1.可排序表的抽象数据类型定义： ADT OrderableList {

数据对象：D = {ai |ai ∈IntegerSet,i = 1,2,……,n,n >= 0} 数据关系：R1 = {|ai-1,ai ∈D.i = 2,……,n} 基本操作： SelectListType(c)

操作结果：打印提示信息，请用户选择待排序表的类型，顺序型、 逆序型还是随机数组。

2

数据结构课程设计 中国海洋大学

BubbleSort(&L)

操作结果：进行起泡排序，返回排序后的顺序表 InsertSort(&L)

操作结果：进行插入排序，返回排序后的顺序表 SelectSort(&L)

操作结果：进行选择排序，返回排序后的顺序表 QuickSort(&L)

操作结果：进行快速排序，返回排序后的顺序表 ShellSort(&L)

操作结果：进行希尔排序，返回排序后的顺序表 HeapSort(&L)

操作结果：进行堆排序，返回排序后的顺序表 SelectSortMethod(&L,c1)

操作结果：打印提示信息，请用户选择排序方法，起泡排序、插入 排序、选择排序、快速排序、希尔排序还是堆排序 OutPut(L)

操作结果：打印排序中关键字的比较次数和移动次数

}ADT OrderableList

2.本程序包含两个模块： 1）.主程序模块 int mian()

3

数据结构课程设计 中国海洋大学

{

初始化；

用户选择待测表的类型； 输入选择，用switch语句判断； While（“命令” ！= “退出”） {

接受命令； 处理命令； } }

２）．可排序表单元模块----实现可排序表的抽象数据类型 各模块之间的调用关系： 主程序模块

可排序表单元模块

三、详细设计

1.根据题目要求何可排序表的基本操作特点，可排序表采用证书顺序表存储结构，并实现在头文件SqList.H。

//******************基本操作的函数原型******************\\\\

#define MAXSIZE 20 //用作示例的顺序表的最大长度 typedef int KeyType; //定义关键字为整数类型

4

数据结构课程设计 中国海洋大学

typedef int InfoType; //定义其他数据项也为整数类型 int time_key_compare = 0; //定义全局变量，关键字比较次 int time_key_move = 0; //数和移动次数均为0 typedef struct {

KeyType key; //关键字项 InfoType otherinfo; //其他数据项

}RedType; //记录类型 typedef struct {

RedType r[MAXSIZE + 1]; //r[0]闲置或用做哨兵 int length; //顺序表长度

}SqList; //顺序表类型 //****************************基本操作*********************\\\\

bool LT(KeyType a,KeyType b)//比较两个KeyType类型变量的大小 {

time_key_compare ++; //比较次数+1 if(a < b)

return true; //<,返回true

else

return false; //否则，返回false

} //LT

5

数据结构课程设计 中国海洋大学

void copyKey(RedType &a,RedType &b)

{ //将RedType类型变量b复制给a

a = b;

time_key_move ++; //关键字移动次数+1

}//copyKey

void swap(RedType &a,RedType &b)

{ //将RedType型变量a和b进行交换操作

RedType c; //定义RedType型变量c c = a; a = b; b = c;

time_key_move += 3; //关键字移动次数+3

}//swap

/****************直接插入排序*********************\\ void InsertSort(SqList &L)

{ //对顺序表L做直接插入排序

for(int i = 2; i <= L.length; ++i) {

if(LT(L.r[i].key,L.r[i - 1].key))

{ //“<”，需将L.r[i]插入有序子表

copyKey(L.r[0] ,L.r[i]); //复制为哨兵 copyKey(L.r[i] ,L.r[i - 1]);

6

数据结构课程设计 中国海洋大学

for(int j = i - 2;LT(L.r[0].key,L.r[j].key); --j) {

copyKey(L.r[j + 1] ,L.r[j]); //记录后移 }

copyKey(L.r[j + 1] ,L.r[0]); //插入到正确的位置

}

}

}//InsertSort

//*************************希尔排序*************************\\ void shellInsert(SqList &L,int dk) { //对顺序表L做一希尔插入排序。 //1.前后记录位置的增量式是dk，而不是1；

//2.r[0]只是暂存单元，不是哨兵。当 j<= 0时，插入位置已找到 for(int i = dk + 1;i <= L.length; ++i) { if(LT(L.r[i].key,L.r[i - dk].key))

{ //需将L.r[i]插入到有序增量子表

copyKey(L.r[0] ,L.r[i]); //暂存在L.r[0]中

for(int j = i - dk;j > 0 && LT(L.r[0].key,L.r[j].key); j-= dk)

copyKey(L.r[j + dk] ,L.r[j]); //记录后移 copyKey(L.r[j + dk] ,L.r[0]); //插入

}

7

数据结构课程设计 中国海洋大学

}

}//ShellInsert

void ShellSort(SqList &L,int dlta[],int t)

{ //按增量序列dlta[0……t - 1]对顺序表L作希尔排序 for(int k = 0;k < t; ++k)

shellInsert(L,dlta[k]); //一趟增量为dlta[k]的插入排序

}//ShellSort

//**************起泡排序****************************\\ void BublleSort(SqList &L) { int i = L.length; while(i > 1) { int lastExchangeIndex = 1; for(int j = 1;j < i ;j ++) { if(LT(L.r[j + 1].key,L.r[j].key)) //小于成立进行交换 { swap(L.r[j + 1],L.r[j]); lastExchangeIndex = j;

}

}

8

数据结构课程设计 中国海洋大学

}

i = lastExchangeIndex;

}//BubbleSort

/***************************简单选择排序********************/ int SelectMinKey(SqList L,int i)

{ //在L.r[i..L.length]中选择key最小的记录 for(int j = i ;j <= L.length; ++j)

}

void SelectSort(SqList &L)

{ //对顺序表做简单选择排序

for(int i = 1;i < L.length; ++i)

{ //选择第i小的记录，并交换到位

int j = SelectMinKey(L,i); { }

return i; //返回最小记录下标

if(LT(L.r[j].key,L.r[i].key)) { }

i = j;

//令j为L.r[i..L.length]中选择key最小的记录

if(i != j)

9

数据结构课程设计 中国海洋大学

}

{ }

swap(L.r[j],L.r[i]); //与第i记录进行交换

}//SelecteSort

/*********************快速排序*************/ int Partition(SqList &L,int low,int high)

{ //交换顺序表L中字表r[low……high]的记录，枢轴记录到位 ，并 //返回其所在位置，此时在他之前（后）的记录均不大（小）与它。

copyKey(L.r[0],L.r[low]);//用字表的第一个纪录作枢轴记录 KeyTypepivotkey=L.r[low].key; //枢轴记录关键字 while(low < high) {

//从表的两端交替向中间扫描

while(lowcopyKey(L.r[low],L.r[high]);

//将比枢轴记录小的记录移到低端

while(low++low;

copyKey(L.r[high],L.r[low]);

//将比枢轴记录大的记录移到高端

}

copyKey(L.r[low],L.r[0]); //枢轴记录到位

return low; //返回枢轴位置

10

数据结构课程设计 中国海洋大学

}//Partition

void QSort(SqList &L,int low,int high)

{ //对顺序表L中的子序列L.r[low……high]做快速排序

if(low < high)

{ //长度> 1

int pivotloc = Partition(L,low,high);

//将L.r[low……high]一分为二

QSort(L,low,pivotloc - 1);

//对低子表递归排序，pivotloc是枢轴位置

QSort(L,pivotloc + 1,high);

//对高子表递归排序 }

}//QSort

void QuickSort(SqList &L)

{ //对顺序表L做快速排序

QSort(L,1,L.length);

}//QuickSort

/*************************堆排序*********************/ void HeapAdjust(SqList &L,int s,int m)

{ //已知L.r[s...m]中记录的关键字除L.r[s].key之外均满足定义， //本函数调整H.r[s]的关键字，使H.r[s...m]成为一个大顶对

RedType rc = L.r[s];

11

数据结构课程设计 中国海洋大学

for(int j = 2 * s;j <= m;j *= 2)

{ //沿key较大的孩子结点向下帅选

if(j < m && LT(L.r[j].key,L.r[j+1].key)) ++j;

//j 为key较大的记录的下标

if(!LT(rc.key,L.r[j].key)) break;//rc应插入在位置s上

copyKey(L.r[s],L.r[j]); s = j;

}

L.r[s] = rc; //插入}//HeapAdjust

void HeapSort(SqList &L) {//对顺序表L进行堆排序

for(int i=L.length/2;i>0;--i)

//把L.r[1....H.length]建成大顶堆

HeapAdjust(L,i,L.length);

for( i = L.length;i >1; --i) {

swap(L.r[1],L.r[i]); //将堆顶记录和当前未经排序的子序列

// L.r[1……i]中最后一个记录进行交换 HeapAdjust(L,1,i - 1);//将L.r[1....i-1]重新调整为大顶堆

}

}//HeapSort

12

数据结构课程设计 中国海洋大学

2.主函数和其他辅助函数的伪码算法

#include //产生随机数所需的库函数 /*****************************主函数************************/ int main() {

int arry[MAXSIZE + 1]; //存放排序前数组

int typeChoice; //根据提示键入的类型选择序号 int methodChoice; //根据提示键入的方法选择序号 int seed; //用于产生随机数的种子 PrintArrayMenu(); //打印选择待排序表的类型菜单 switch(typeChoice)

{

case 1:选择的是顺序表，初始化链表并打印

break;

case 2:选择的是逆序表，初始化链表并打印

break;

case 3:选择的是随机数表

srand(seed);

//初始化随机数，并利用rand（）产生随机数并打印

break;

default:

break;

13

数据结构课程设计 中国海洋大学

}

cout <getChoice(L,choice);

//根据选择的方法堆表进行排序操作并打印相关信息 }

/****************根据选择排序********************/ void getChoice(SqList &L,int c)

{ //根据选择进行排序并输出相关信息

int Array[3] = {5,3,1}; //希尔排序所需增量数组 switch(c) { case 1:

InsertSort(L); // 直接插入排序 for( j = 1;j <= MAXSIZE; j ++) } return 0;

{ //将链表恢复至未排序时状态 L.r[j].key = arry[j]; }

14

数据结构课程设计 中国海洋大学

outPut(L); break;

//输出关键字比较次数和移动次数

case 2: ShellSort(L,Array,3); //希尔排序 outPut(L); //输出关键字比较次数和移动次数

break;

case 3: BublleSort(L); outPut(L);

break;

case 4: SelectSort(L); outPut(L);

break;

case 5: QuickSort(L); outPut(L);

break;

case 6: HeapSort(L); outPut(L);

break;

//起泡排序 //输出关键字比较次数和移动次数 //简单选择排序 //输出关键字比较次数和移动次数 //快速排序 //输出关键字比较次数和移动次数 //堆排序 //输出关键字比较次数和移动次数 15

数据结构课程设计 中国海洋大学

}

case 7:排序结束 default: }

break;

3.函数的调用关系图反映了程序的层次结构

InsertSort 顺序表 ShellSort 主程 BublleSort

序 逆序表 getTypeChoice getMethodChoice SelectSort

随机数表 QuickSort HeapSort srand rand

四、排序算法结果比较

16

数据结构课程设计

简单选择排序 209/0 209/30 209/51 209/45 209/42 209/48 209/51 50004999/29976 50004999/299 50004999/29970 50004999/29982 50004999/29967

中国海洋大学

测试 直接插入排序 顺序表 逆序表 随即表1 随即表2 随即表3 随即表4 随即表5 随即表6 随即表7 随即表8 随即表9 随即

19/0 209/228 134/147 106/119 99/108 123/134 140/153 24962887/24972872

25067619/25077602

24951520/24961493

25231354/25241327

24940230/2495

希尔排序 51/0 110/108 105/85 119/101 107/84 117/98 105/85 5153988/5146226 5161759/5153799 5183866/5176131 5240599/5232732 5166043/5158198

起泡排序 19/0 190/570 184/345 174/261 165/240 176/312 1/363 49981281/748586 499521/75172860 49904576/74824563 49959846/756065 49952854/74790693

快速排序 190/76 200/76 105/76 114/72 107/74 104/82 119/72 2260/75760 225821/76130 223755/75818 216797/75786 210437/76844

堆排序 121/118 105/100 115/109 118/109 119/118 109/106 107/101 235476/144261 235408/144248 235241/144179 235488/144253 235432/144304

表长 20 20 20 20 20 20 20 10000 10000 10000 10000 10000

表10 0219

对各种表长和测试组数进行了测试，程序运行正常。分析实测得到的数值，六种排序算法的特点小结如下：

测试

直接插入排序 希尔排序

起泡排序

简单选择排序

比较次数

第三多 越乱越多 第二多 越乱越多

第三少 第二多 乱否差异小

越乱越多

最 多 最少 第二少 与乱否无关

移动次数

第三多 最多 越乱越多

最少

第二少 乱否差异小

第三少 乱否差异小

越乱越多 乱否差异小

乱否差异小

乱否差异小

快速排序

堆排序

五、附录

17

数据结构课程设计 中国海洋大学

源程序文件名清单：

SqList.H //可排序表的实现 main.C //主程序 六、实验中遇到的问题及解决办法

1.程序采取循序渐进的策略。首先设计和实现可排序表的建立操作，根据要求因包括随机数序列、正序和逆序三种情况，为避免不必要的错误，程序采用了先定义了两个数组，分别为正序和逆序，程序运行时分别将数组的值赋给链表的方式进行顺序表的建立，另外，起初对于随机数的产生产生了疑惑，但随后通过搜集资料成功的使用srand（seed）和rand（）函数得到解决。然后用插入排序验证了各种内部辅助操作的正确性，进而逐个加入其他排序算法，最后完成对测试结果的显示。

2.程序旨在进行六种排序方法优劣性的比较，在进行对六种排序依次排序时，出现了进行过依次排序后，排序表变为正序表而之后的集中排序方法都是在进行正序表的排序，而没有达到想要的效果，最后在主函数中添加了一个数组，用于记录原排序表的顺序，并在每次排序之后利用该数组对排序表进行再次建立，使得问题成功解决。

3.开始编程之初，总会出现关键字比较和移动次数的计算错误，在程序中进行逐步记录既繁琐又易出错，之后经过思考，建立了copyKey（）和swap（）函数，成功提高了程序效率并降低了计算错误率。

18