排序算法比较

课程设计说明书

设计名称： 数据结构课程设计

题 目： 排序算法比较

学生姓名：

专 业： 计算机科学与技术 班 级： 11级一班 学 号：

指导教师： 李娅 日 期： 2013 年 3 月 20 日

1

课程设计任务书

计算机科学与技术 专业 11 年级 班 一、 设计题目 各种算法排序比较 二、 主要内容

利用随机函数产生N个随机整数（N<10000），对这些数进行多种方法排序。

三、 要求

1)至少采用4种方法实现上述问题求解（可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序），并把排序后的结果保存在不同的文件里。

2）给出该排序算法对数据的比较次数和移动次数并统计每一种排序方法的性能（以运行程序所花费的时间为准进行对比），找出其中两种较快的方法。

四、 进度安排

1）资料阅读查找、系统分析，概要设计；时间安排0.5天 2）系统详细设计、功能设计；时间安排0.5天 3）算法实现、编程调试；时间安排1天

4）资料整理、课程设计说明书编写。时间安排1天 五、 完成后应上交的材料

给出系统的概要设计、详细设计；完成核心算法的实现；完成规范化的课程设计说明书的编写。

课程设计的总结报告，还应包括以下内容：

1

（1）课程设计中遇到的主要问题和解决方法； （2）创新和得意之处；

（3）课程设计存在的不足，需进一步改进的设想； （4）课程设计的感想和心得体会。

以上内容均填写在《课程设计说明书》上，要求干净整洁，符合课程设计的要求和规范。

六、 总评成绩

1

指导教师 签名日期 年 月 日

系 主 任 审核日期 年 月 日

1

目 录

排序算法比较

一、需求析..................................2 二、程序的主要能............................2 三、程序运行台..............................3 四、算法及时间复度..........................3 五、测试结果................................5 六、程序源代码..............................6 七、感想体会与总结.........................13

- 1 - 1

排序算法比较

一、主要内容：

利用随机函数产生N个随机整数（N<10000），对这些数进行多种方法排序。 具体要求：

1)至少采用4种方法实现上述问题求解（可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序），并把排序后的结果保存在不同的文件里。

2）给出该排序算法对数据的比较次数和移动次数并统计每一种排序方法的性能（以运行程序所花费的时间为准进行对比），找出其中两种较快的方法。

二、程序的主要功能

1.用户输入随机数的个数n

2.随机数在排序函数作用下进行排序

3.程序给出随机数的移动次数yd、比较次数bj、以及排序所用的时间。

三、程序运行平台

- 2 - 1

Visual C++ 6.0版本

四、算法及时间复杂度

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

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

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

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

找和插入，这个查找可利用折半查找来实现，即为折半插入排序。

（3）起泡排序：首先将第一个记录的关键字和第二个记录的关键字

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

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

中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。 （5）选择排序：通过N-I次关键字间的比较，从N-I+1个记录中选

出关键字最小的记录，并和第I（1<=I<=N）个记录交换。 （二）时间复杂度分析

- 3 - 1

排序算法 插入排序 冒泡排序 快速排序 选择排序 最差时间 O(n2) O(n2) O(n2) O(n2) 时间复杂度 O(n2) O(n2) O(n*log2n) O(n2) 是否稳定？ 稳定 稳定 不稳定 稳定

10000个数据的时间比较：

算法名称 直接插入排序 折半插入排序 起泡排序 快速排序 选择排序 用时 0.25 0.219 0.704 0.016 0.39

五、测试结果

1、首先选择需要排序的数字个数，比如输入n=100

- 4 - 1

2、再选择用哪种方法进行排序，比如输入方法1

3、各种方法排序显示已排序方法的信息5

六、程序源代码

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

第二题：排序算法比较

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

利用直接插入排序、折半插入排序，起泡排序、快速排序、选择排序四种排序方法

（可添加其它排序方法）进行排序（并统计每一种排序所耗费的时间，比较次数，移动次数）

************************************************************************************************/ #include #include #include #include #define MAXSIZE 9999 typedef int Keytype;

- 5 - 1

typedef struct { Keytype r[MAXSIZE+1];//储存数值 int length;//数组大小 }Sqlist;

typedef struct { int NumberOfJudgement;//比较次数 int NumberOfMovement;//移动次数 double time;//排序所用时间 }S_time;

typedef struct { S_time Sort[4]; int n; }Sort_result;

/*****************排序结果****************/ void print(Sqlist* L) { int i; for(i=1;i<=L->length;i++) { printf(\第M个数%-5d|\ if(!(i%5)) printf(\ } }

/****************插入排序****************/ void InsertSort(Sqlist* L,Sort_result* T) { int i,j; for(i=2;i<=L->length;++i) { T->Sort[0].NumberOfJudgement++; if(L->r[i]r[i-1]) { T->Sort[0].NumberOfMovement++; L->r[0]=L->r[i]; L->r[i]=L->r[i-1]; for(j=i-2;L->r[0]r[j];j--) { T->Sort[0].NumberOfJudgement++; T->Sort[0].NumberOfMovement++; L->r[j+1]=L->r[j];

- 6 - 1

} L->r[j+1]=L->r[0]; } } }

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

void ShellInsert(Sqlist* L,int dk,Sort_result* T) { int i,j; for(i=dk+1;i<=L->length;i++) { T->Sort[1].NumberOfJudgement++; if(L->r[i]r[i-dk]) { L->r[0]=L->r[i]; for(j=i-dk;j>0&&L->r[0]r[j];j-=dk) { T->Sort[1].NumberOfJudgement++; T->Sort[1].NumberOfMovement++; L->r[j+dk]=L->r[j]; } L->r[j+dk]=L->r[0]; } } }

void Shellsort(Sqlist* L,int dlta[],int t,Sort_result* T) { int k; for(k=0;k

}//shellsort

/***********冒泡排序法*******************/ void Bubblesort(Sqlist* L,Sort_result* T) { int i,j,temp; for(i=1;i<=L->length;i++) { for(j=i+1;j<=L->length;j++) { T->Sort[2].NumberOfJudgement++; if(L->r[i]>L->r[j]) {

- 7 - 1

T->Sort[2].NumberOfMovement++; temp=L->r[i]; L->r[i]=L->r[j]; L->r[j]=temp; } } } }

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

int Partition(Sqlist* L,int low,int high,Sort_result* T) { int pivotkey; L->r[0]=L->r[low]; pivotkey=L->r[low]; while(lowSort[3].NumberOfJudgement++; while(lowr[high]>=pivotkey) { T->Sort[3].NumberOfJudgement++; --high; } T->Sort[3].NumberOfMovement++; L->r[low]=L->r[high]; while(lowr[low]<=pivotkey) { T->Sort[3].NumberOfJudgement++; ++low; } T->Sort[3].NumberOfMovement++; L->r[high]=L->r[low]; } L->r[low]=L->r[0]; return low; }

void Qsort(Sqlist* L,int low,int high,Sort_result* T) { int pivotloc; T->Sort[3].NumberOfJudgement++; if(low

- 8 - 1

} }

void Quicksort(Sqlist* L,Sort_result* T) { Qsort(L,1,L->length,T); }

/***********选择排序方法*****************/

void sort(int* choose,Sqlist* L,Sort_result* T) { int i; clock_t start,end; FILE* fp; char sortname[4][50]={\插入排序\希尔排序\起泡排序\快速排序\ char fname[4][50]={\插入排序结果.txt\希尔排序结果.txt\起泡排序结果.txt\快速排序结果.txt\ int dlta[]={5000,2500,1250,625,313,167,79,39,23,1},t=10;//增量序列和数列大小 if(*choose!=5) { fp=fopen(fname[*choose-1],\ if(!fp) { printf(\打开文件失败\ exit(1); } } switch(*choose) { case 1: { printf(\现在开始插入排序\\n\ start=clock(); InsertSort(L,T); end=clock(); break; } case 2: { printf(\现在开始希尔排序\\n\ start=clock(); Shellsort(L,dlta,t,T); end=clock(); break; }

- 9 - 1

case 3: { printf(\现在开始起泡排序\\n\ start=clock(); Bubblesort(L,T); end=clock(); break; } case 4: { printf(\现在开始快速排序\\n\ start=clock(); Quicksort(L,T); end=clock(); break; } case 5: { if(T->n==0) printf(\请先使用任意一种排序方法再查阅排序方法的信息\ else for(i=0;i<4;i++) { if(T->Sort[i].NumberOfJudgement) printf(\排序：移动元素次数:%d 判断次数:%d 所用时间:%lf\\n\ ,sortname[i],T->Sort[i].NumberOfMovement,T->Sort[i].NumberOfJudgement,T->Sort[i].time); } } } if(*choose==5) getchar(); else { T->Sort[*choose-1].time=(double)(end-start); T->n++; print(L);//显示排序结果 for(i=1;i<=L->length;i++) { fprintf(fp,\第M个数%-5d|\ if(!(i%5)) fprintf(fp,\ } fclose(fp);

- 10 - 1

fp=NULL; getchar(); } getchar(); *choose=0; }

/**************主函数********************/ int main() { Sqlist L;//存放待排序数值的数组 Sort_result T;//存放 排序的比较次数和移动次数 int i,a,choose=0,arr[MAXSIZE+1];// choose功能选择 srand(time(NULL)); printf(\请输入需要排序的数字个数:\ scanf(\ L.length=a;//取1-9999的随机数 printf(\ printf(\要排列%d个整数\\n\ printf(\ getchar(); for(i=1;i<=L.length;i++)//生成N个随机数 { L.r[i]=rand()000+1; } for(i=1;i<=L.length;i++)//把随机数组放到备份数组中 { arr[i]=L.r[i]; } for(i=1;i<=L.length;i++) { printf(\第M个数%-5d|\ if(!(i%5)) printf(\ } getchar(); for(i=0;i<4;i++)//初始化排序的比较次数和移动次数 { T.Sort[i].NumberOfJudgement=0; T.Sort[i].NumberOfMovement=0; } T.n=0; for(;;) { for(;choose<1||choose>6;)

- 11 - 1

{ system(\ printf(\================\\n\ printf(\插入排序 2.希尔排序 3.起泡排序 4.快速排序 5.显示已使用排序方法的信息 6.退出\\n\ printf(\================\\n\ printf(\请输入你需要功能的序号:\ scanf(\ if(choose<1||choose>6) printf(\请重新输入序号\\n\ if(choose==6) exit(0); } sort(&choose,&L,&T);//调用排序函数 if(choose!=5) { for(i=1;i<=L.length;i++) { L.r[i]=arr[i];//每次排序后恢复原始数据 } } } getchar(); return 0; }

七、 感想体会与总结

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

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

2、做任何事情我决定都应该有个总体规划。之后的工作按照规划逐步展开完成。对于一个完整的程序设计，首先需要总体规划写

- 12 - 1

程序的步骤，分块写,分函数写，然后写完一部分马上纠错调试。而不是像我第一次那样，一口气写完，然后再花几倍的时间调试。一步步来，走好一步再走下一步。

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

4、通过这次课设，不仅仅复习了C语言相关知识、 而且也了解并初步掌握了c++,通过这一次课程设计,磨练了我的意志,是我更有了自信心。

- 13 - 1

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