数据结构课程设计——排序算法比较

XXXXXX大学

《数据结构》课程设计报告

班级： 学号： 姓名： 指导老师：

第 1 页 共 20 页

数据结构课程设计——排序算法比较

目 录

排序算法比较

一、需求分析

二、程序的主要功能 三、程序运行平台 四、数据结构

五、算法及时间复杂度 六、测试用例 七、程序源代码

二 感想体会与总结

第 2 页 共 20 页

数据结构课程设计——排序算法比较

排序算法比较

一、需求分析

利用随机函数产生N个随机整数（N = 500，1000，1500，2000，2500，…,30000），利用直接插入排序、折半插入排序，起泡排序、快速排序、选择排序、堆排序，基数排序七种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间（统计为图表坐标形式）。

二、程序的主要功能

1.用户输入任意个数，产生相应的随机数

2.用户可以自己选择排序方式（直接插入排序、折半插入排序、起泡排序、快速排序、选择排序、堆排序、基数排序）的一种

3.程序给出原始数据、排序后从小到大的数据，并给出排序所用的时间。

三、程序运行平台

Visual C++ 6.0版本

四、数据结构

本程序的数据结构为线形表，线性顺序表、线性链表。 。

1、结构体： typedef struct {

int *r; //r指向线形表的第一个结点。 r[0]闲置，不同的算法有不同

的用处，如用作哨兵等。

int length; //顺序表的总长度 }Sqlist;

2、空线性表

Status InitSqlist(Sqlist &L) { L.r=(int *)malloc(MAXSIZE*sizeof(int)); //分配存储空间 if(!L.r) { printf(\存储分配失败！\ exit(0); } //存储分配失败

第 3 页 共 20 页

数据结构课程设计——排序算法比较

}

L.length=0;//初始长度为0 return OK;

五、算法及时间复杂度

（一）各个排序是算法思想：

（1）直接插入排序：将一个记录插入到已排好的有序表中，从而得到一

个新的，记录数增加1的有序表。

（2）折半插入排序：插入排序的基本插入是在一个有序表中进行查找和

插入，这个查找可利用折半查找来实现，即为折半插入排序。 （3）起泡排序：首先将第一个记录的关键字和第二个记录的关键字进行

比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直到第N-1和第N个记录的关键字进行过比较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序，对前N-1个记录进行同样操作。一共要进行N-1趟起泡排序。

（4）快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一

部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。

（5）选择排序：通过N-I次关键字间的比较，从N-I+1个记录中选出关

键字最小的记录，并和第I（1<=I<=N）个记录交换。

（6）堆排序：在堆排序的算法中先建一个大顶堆，既先选得一个关键字

作为最大的记录并与序列中最后一个记录交换，然后对序列中前N-1记录进行选择，重新将它调整成一个大顶堆，如此反复直到排序结束。

（7）基数排序：按最低位优先法先对低位关键字进行排序，直到对最高

位关键字排序为止，经过若干次分配和收集来实现排序 （二）时间复杂度分析

排序算法 插入排序 冒泡排序 最差时间 O(n2) O(n2) 时间复杂度 O(n2) O(n2) 是否稳定？ 稳定 稳定 第 4 页 共 20 页

数据结构课程设计——排序算法比较

快速排序 选择排序 堆排序 基数排序 O(n2) O(n2) O(n*log2n) O(n*log2n) O(n*log2n) O(n2) O(n*log2n) O(n2) 不稳定 稳定 不稳定 稳定 10000个数据的时间比较： 算法名称 直接插入排序 折半插入排序 起泡排序 快速排序 选择排序 堆排序 基数排序 用时 0.25 0.219 0.704 0.016 0.39 0.0001 0.016 六、测试用例

1、首先选择需要排序的数字个数，比如输入5000。

第 5 页 共 20 页

数据结构课程设计——排序算法比较

2、系统显示出随机产生的随机数。

用户选择排序方式，比如选择1.直接插入排序

第 6 页 共 20 页

数据结构课程设计——排序算法比较

3、系统将随机数排序后整齐的显示出来。

4、用户可以选择继续排序或者退出系统。

七、程序源代码

/********************************************************************************************** 第六题：排序算法比较

设计要求：利用随机函数产生N个随机整数（N = 500，1000，1500，2000，2500，…,30000），

第 7 页 共 20 页

数据结构课程设计——排序算法比较

利用直接插入排序、折半插入排序，起泡排序、快速排序、||选择排序、堆排序，基数排序七种排序方法

（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一种排序所耗费的时间（统计

为图表坐标形式）。

************************************************************************************************/ #include \#include \

#include \计时

#define ERROR 0 #define OK 1

#define OVERFLOW -2

#define MAXSIZE 100000 //用户自己规定排序的数字的长度

typedef int Status;

typedef struct {

int *r; // r[0]闲置

int length; //顺序表的总长度 }Sqlist;

//构造一个空线性表

Status InitSqlist(Sqlist &L) { L.r=(int *)malloc(MAXSIZE*sizeof(int)); //分配存储空间 if(!L.r) { printf(\存储分配失败！\ exit(0); } //存储分配失败 L.length=0;//初始长度为0 return OK; }

//输入随机数并显示在界面上

Status ScanfSqlist(int &N,Sqlist &L) { int i; printf(\请输入要排序的元素个数N: \ scanf(\ for(i=1;i<=N;i++) L.r[i]=rand(); //随机产生样本整数

第 8 页 共 20 页

数据结构课程设计——排序算法比较

printf(\ printf(\ 随机产生了%d个随机数，它们是：\\n\ for(i=1;i<=N;i++) { printf(\ \ } printf(\ L.length=N; //存储线性表的长度 return OK; }

//输出排序之后的数据

Status PrintfSqlist(int N,Sqlist L) { int i; printf(\数据个数：\输出数据个数 printf(\ printf(\排序后的数据：(从左向右依次增大)\\n\输出数据 for(i=1;i<=N;i++) printf(\ \ printf(\ return OK; }

//*************************************************************** // 直接插入排序

//*************************************************************** Status InsertSort(Sqlist &L) //参考书P265算法10.1 { int i,j; if(L.length==0) { printf(\要排序的数据为空！\ return ERROR; } for(i=2;i<=L.length;i++) { if(L.r[i]

第 9 页 共 20 页

数据结构课程设计——排序算法比较

for(j=i-2;L.r[0]

//*************************************************************** // 折半插入排序

//*************************************************************** Status BInsertSort(Sqlist &L) //参考书P267算法10.2 { int i,j,mid,low,high; if(L.length==0) { printf(\要排序的数据为空！\ return ERROR; } for(i=2;i<=L.length;i++) { L.r[0]=L.r[i]; //将L.r[i]暂存在L.r[0] low=1; high=i-1; while(low<=high) //在r[low..high]中折半查找有序插入的位置 { mid=(low+high)/2; if(L.r[0]=high+1;j--) //插入点后的数据后移 { L.r[j+1]=L.r[j]; } L.r[high+1]=L.r[0]; //将数据插入

第 10 页 共 20 页

数据结构课程设计——排序算法比较

}//for return OK; }

/******************************************************************************** 希尔排序

*********************************************************************************/

//参考书P272算法10.4及10.5

/*Status ShellInsert(Sqlist &L,int dk) //希尔插入排序 { int i,j; //前后位置的增量是dk for(i=dk+1;i<=L.length;i++) //r[0]只是暂存单元，不是哨兵， { if(L.r[i]0 && L.r[0]

Status ShellSort(Sqlist &L,int dlta[5],int t) //希尔排序 { int i; if(L.length==0) { printf(\要排序的数据为空！\ return ERROR; } for(i=0;i

//一趟增量第 11 页 共 20 页

数据结构课程设计——排序算法比较

} return OK; } */

//************************************************************** // 起泡排序

//************************************************************** Status BubbleSort(Sqlist &L) { int i,j,t; if(L.length==0) { printf(\要排序的数据为空！\ return ERROR; } for(i=1;i<=L.length-1;i++) { for(j=1;j<=L.length-i;j++) { if(L.r[j]>L.r[j+1]) //前面的数据>后面数据时 { t=L.r[j+1]; L.r[j+1]=L.r[j]; L.r[j]=t; //将元素交换 } } } return OK; }

//**************************************************** // 快速排序

//****************************************************

int Partition(Sqlist &L, int low, int high) //交换顺序表中子表L.r[low..high]的记录，使得枢轴记录到位，并返回其所在位置，此时在它之前（后）的记录均不大于它 { int pivotkey; //记录关键字 L.r[0]=L.r[low]; //用子表的第一个纪录作枢轴纪录 pivotkey=L.r[low]; //用枢轴纪录关键字 while (low=pivotkey)

第 12 页 共 20 页

数据结构课程设计——排序算法比较

{ high--; } L.r[low]= L.r[high]; //将比枢轴记录小的记录移到低端 while(low

L.r[low]=L.r[0]; //枢轴记录到位 return low; }//Partition函数

void Qsort (Sqlist &L,int low, int high) { int pivotloc; if (low

Status QuickSort (Sqlist &L) {

if(L.length==0) { printf(\要排序的数据为空！\ return ERROR; } Qsort(L,1,L.length); return OK; }//QuickSort

//********************************************** // 选择排序

//********************************************** Status ChooseSort(Sqlist &L) { int i,j,k,t; if(L.length==0) { printf(\没有数据！\ return ERROR;

第 13 页 共 20 页

数据结构课程设计——排序算法比较

} for(i=1;i<=L.length;i++) //排序的趟数 { k=i; for(j=i+1;j<=L.length;j++) //比较第i个元素以及其后的数据中最小的 { if(L.r[j]

//**************************************** // 堆排序

//****************************************

Status HeapAdjust(Sqlist &L,int s,int m) //调整L.r[s]的关键字,使L.r[s~m]成大顶堆 { int i; L.r[0]=L.r[s]; for(i=2*s;i+1<=m;i*=2) //沿数据较大的孩子结点向下筛选 { if(i=L.r[i]) //L.r[0]插入在S位置上 break; L.r[s]=L.r[i]; s=i; } L.r[s]=L.r[0]; //插入新数据 return OK; }

Status HeapSort(Sqlist &L) //堆排序 { int i,t;

第 14 页 共 20 页

数据结构课程设计——排序算法比较

if(L.length==0) { printf(\没有数据！\ return ERROR; } for(i=L.length/2;i>0;i--) HeapAdjust(L,i,L.length); for(i=L.length;i>1;i--) { t=L.r[1]; //将堆顶记录和当前未经排序的子序列L.r[1..i]中最后一个记录互换 L.r[1]=L.r[i]; L.r[i]=t; HeapAdjust(L,1,i-1); //将L.r[1..i-1]重新调整为大顶堆 } return OK; }

//************************************************** // 基数排序

//************************************************** typedef struct node{ int key; node *next; }RecType;

Status RadixSort(Sqlist L) { int t,i,j,k,d,n=1,m; RecType *p,*s,*q,*head[10],*tail[10]; //定义各链队的首尾指针 for(i=1;i<=L.length;i++) //将顺序表转化为链表 { s=(RecType*)malloc(sizeof(RecType)); s->key=L.r[i]; if(i==1) //当为第一个元素时 { q=s; p=s; t++; } else { q->next=s; //将链表连接起来 q=s; t++;

第 15 页 共 20 页

数据结构课程设计——排序算法比较

} q->next=NULL; }

d=1;

while(n>0) //将每个元素分配至各个链队 { for(j=0;j<10;j++) //初始化各链队首、尾指针 { head[j] = NULL; tail[j] = NULL; } while(p!=NULL) //对于原链表中的每个结点循环 { k=p->key/d; k=k; if(head[k]==NULL) //进行分配 { head[k]=p; tail[k]=p; } else { tail[k]->next=p; tail[k]=p; } p=p->next; //取下一个待排序的元素 } p=NULL; //用于收集第一个元素时的判断 for(j=0;j<10;j++) //对每一个链队循环， 搜集每一个元素 { if(head[j]!=NULL) //进行搜集 { if(p==NULL) { p=head[j]; q=tail[j]; } else { q->next=head[j]; q=tail[j]; } } } q->next=NULL; //最后一个结点的next置为空 d=d*10;

第 16 页 共 20 页

数据结构课程设计——排序算法比较

n=0; m=1; while(m<=L.length) //判断当L中的元素都除d后是不是都为零了 { if((L.r[m]/d)!=0) { n++; m++; } else m++; } } i=1; while(p!=NULL) //将链表转换为顺序表 { L.r[i]=p->key; i++; p=p->next; } return OK; }

//************************************** // 主函数 //************************************** void main() { Sqlist L; Sqlist L0; InitSqlist(L); //初始化L InitSqlist(L0); int m,i; char choice='z'; clock_t start, finish; //定义clock_t用于计时 double duration; //向L中输入元素 printf(\n █████████████████████████████████████\\n\ printf(\ \\n\ printf(\ 算法排序比较系统 \\n\ printf(\ \\n\ printf(\ █████████████████████████████████████\\n\

第 17 页 共 20 页

数据结构课程设计——排序算法比较

printf(\ 以下是各个排序算法的代号：\\n\\n\ printf(\ 1、直接插入排序 \\n\ printf(\ 2、折半插入排序 \\n\ printf(\ 3、起泡排序 \\n\ printf(\ 4、快速排序\\n\ printf(\ 5、选择排序\\n\ printf(\ 6、堆排序\\n\ printf(\ 7、基数排序\\n\ printf(\ 8、退出该系统\\n\\n\ ScanfSqlist(m,L0); printf(\ printf(\ 1、直接插入排序 \\n\ printf(\ 2、折半插入排序 \\n\ printf(\ 3、起泡排序 \\n\ printf(\ 4、快速排序\\n\ printf(\ 5、选择排序\\n\ printf(\ 6、堆排序\\n\ printf(\ 7、基数排序\\n\ printf(\ 8、退出该系统\\n\\n\ printf(\请选择排序的方式,数字1-7: \ scanf(\ //选择排序方式赋值choice，用于后面的函数选择 while(choice<1||choice>8) { printf(\输入方式有误。\\n请输入1-7选择排序方式，或者选择8退出系统\ scanf(\ } while(choice!=8) { for(i=1;i<=L0.length;i++) L.r[i]=L0.r[i]; L.length=L0.length; switch(choice) { case 1://直接插入排序 start = clock(); InsertSort(L); finish = clock(); break; case 2://折半插入排序 start = clock(); BInsertSort(L); finish = clock();

第 18 页 共 20 页

数据结构课程设计——排序算法比较

break; case 3://起泡排序 start = clock(); BubbleSort(L); finish = clock(); break; case 4://快速排序 start = clock(); QuickSort(L); finish = clock(); break; case 5://选择排序 start = clock(); ChooseSort(L); finish = clock(); break; case 6://堆排序 start = clock(); HeapSort(L); finish = clock(); break; case 7://基数排序 start = clock(); RadixSort(L); finish = clock(); break; case 8://直接退出 break; } PrintfSqlist(m,L); //输出数据和L的长度 duration = (double)(finish - start) / CLOCKS_PER_SEC; //输出算术时间 printf(\本次排序运算所用的时间是：%lf seconds\\n\

printf(\ 本次排序结束。\\n\ printf(\

___________________________________________________________________\\n\ printf(\ 继续本系统吗？\\n\\n\

printf(\ 以下是各个排序算法的代号：\\n\ printf(\ 1、直接插入排序\\n\ printf(\ 2、折半插入排序\\n\ printf(\ 3、起泡排序\\n\ printf(\ 4、快速排序\\n\ printf(\ 5、选择排序\\n\

第 19 页 共 20 页

数据结构课程设计——排序算法比较

printf(\ 6、堆排序\\n\

printf(\ 7、基数排序\\n\ printf(\ 8、退出该系统\\n\ printf(\请请输入1-7选择排序方式，或者选择8退出系统:\ scanf(\ while(choice<1||choice>8) { printf(\输入方式有误。\\n请输入1-7选择排序方式，或者选择8退出系统\ scanf(\ } }

}

感想体会与总结

好的算法＋编程技巧＋高效率＝好的程序。

1、做什么都需要耐心，做设计写程序更需要耐心。一开始的时候，我写函数写的很快，可是等最后调试的时候发现错误很隐蔽，就很费时间了。后来我先在纸上构思出函数的功能和参数，考虑好接口之后才动手编，这样就比较容易成功了。

2、做任何事情我决定都应该有个总体规划。之后的工作按照规划逐步展开完成。对于一个完整的程序设计，首先需要总体规划写程序的步骤，分块写分函数写，然后写完一部分马上纠错调试。而不是像我第一个程序，一口气写完，然后再花几倍的时间调试。一步步来，走好一步再走下一步。写程序是这样，做项目是这样，过我们的生活更是应该这样。

3、感觉一开始设计结构写函数体现的是数据结构的思想，后面的调试则更加体现了人的综合素质，专业知识、坚定耐心、锲而不舍，真的缺一不可啊。

4、通过这次课设，不仅仅复习了C语言相关知识、巩固了数据结构关于栈和排序的算法等知识，更磨练了我的意志。

第 20 页 共 20 页