基于C语言的多种排序方法的实现

1 引 言

1.1 课题背景

排序问题源远流长，一直是数学地重要组成部分。随着各种信息的快速更新，排序问题也走进了其他领域以及我们地日常生活。如何高效地排序一直困扰着我们。

1.2 课程设计目的

排序是数学的重要组成部分，工作量大是其存在的问题。如何高效地排序？本程序就是解决这个问题而设计。程序中，把数列储存在数组中，采用插入排序等十种排序方法对数组元素进行排序，高效地解决了排序问题。本软件开发的平台为最新的微软公司出版的市面最新系统Windows 2000，而且可以作为自身的运行平台非常广泛，包括 Windows 98/2000/XP/Vista等等。

1.3课程设计内容

本程序把对数列的排序转化为对数组元素的排序，用户可以根据自己的实际问题选择系统提供的七种排序方法的任意一种进行排序。程序通过自身的判断以及处理实现排序。程序最后输出每趟排序及初始排序结果。

2 系统分析与设计方案

2.1 系统分析

设计一个排序信息管理系统，使之能够操作实现以下功能： 1) 显示需要输入的排序长度及其各个关键字 2) 初始化输入的排序序列 3) 显示可供选择的操作菜单

4) 显示输出操作后的移动次数和比较次数 5) 显示操作后的新序列 5) 可实现循环继续操 2.2 设计思路

通过定义C语言顺序表来存储排序元素信息，构造相关函数，对输入的元素进行相应的处理。 [2] 2.3 设计方案

设计方案如图2.1所示

开始 定义顺序表 相关函数的声明 主函数 退出系统 图2.1 设计方案

具体流程见图2.2

开始

菜单 插入排序 冒泡排序 退出排序 快速排序 堆排序 折半插入排序 简单选择排序 输入数据 是否继续操作 结束 图2.2 程序流程图

3功能设计

3.1 SqList顺序表

其中包括顺序表长度，以及顺序表。源代码如下：[1] typedef struct {

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

}RedType;

typedef struct {

RedType r[MaxSize+1]; //r[0]作为监视哨 int length; //顺序表长度 }SqList;

3.2 直接插入排序

直接插入排序是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表

有序序列r[1……i-1] 无序系列r[i……n] r[i] 有序序列r[1……i] 无序系列r[i+1……n] 图3.1 直接插入排序示意图

将第i个记录的关键字r[i].key顺序地与前面记录的关键字r[i-1].key,r[i-2].key,……，r[1].key进行比较，把所有关键字大于r[i].key的记录依次后移一位，直到关键字小于或者等于r[i].key的记录r[j]，直接将r[i]插入到r[j]后面，循环以上过程直到最后一个纪录也插入到合理的位置。整个排序过程是从第2个记录开始的，视第1个记录为已经排好序的集合。

3.3 冒泡排序

冒泡排序是对所有相邻的记录进行比较，若这两个元素刚好与排序结果逆序，则将这两个元素的位置进行交换。 过程描述如下图所示：

交换 交换 13.25 13.15 13.02 12.92 12.95 13.10

13.15 13.02 12.92 12.95 13.10 13.25 图3.3 冒泡排序的第一趟比较结果

13.15 13.25 13.02 12.92 12.95 13.10 交换 13.15 13.02 13.25 12.92 12.95 13.10 图3.2 冒泡排序第一趟的前三次比较

（1）、将整个的待排序序列的记录序列划分为有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录。

（2）、对无序区从前向后依次将相邻记录的数据进行比较，若两结果的大小刚好与排序结果相反，则将其交换，从而始数据值大的记录向右边移动。计较完无序区的最后两个记录，一趟冒泡排序结束。无序区最后一个记录进入有序区。 （3）、重复步骤（2），直到无序区中只剩下一个记录。

3.4 快速排序

快速排序是首先选择一个轴值，通过一趟排序将待排记录分割成的两部分，其中一部分记录的关键均小于等于轴值，另一部分记录的关键字均大于等于轴值，再分别对这两部分继续进行排序，以达到整个序列有序。

过程描述路下图所示：

初始关键字序列 72 6 57 88 60 42 83 73 48 85

i j j

进行1次交换之后 48 6 57 88 60 42 83 73 85

i i j

进行2次交换之后 48 6 57 60 42 83 73 88 85

I j j

进行3次交换之后 48 6 57 42 60 83 73 48 85

I j j

完成一趟排序 48 6 57 42 60 72 83 73 88 85

图3.4 一趟快速排序过程

初始状态 {72 6 57 88 60 42 83 73 48 85}

一次划分之后 {48 6 57 42 60} 72 {83 73 48 85}

分别进行快速排序 {42 6} 48 {57 60} {6} 42 结束

57 {60} 结束

{73} 83 {88 85} 结束

{85} 88 结束

有序序列 {6 42 48 57 60 72 73 83 85 88}

图3.5 快速排序的完整过程

3.5 堆排序

（1）、用建堆算法建立原始堆； （2）、堆尾元素与堆顶元素互换； （3）、再次调用建堆算法建堆；

（4）、重复执行步骤（2）直到所有元素排好序。

过程描述：

假设，待排序的序列为：36 15 53 18 45 30 48 72 93 第一步，建立原始堆结构

36 36

15 53 15 53

18 45 30 48 18 45 30 48

93 72 93 72

a、从第4个节点开始调整 b、对第3个节点进行调整 36 15 30 15 36 30 18 45 53 48 18 45 30 48 72 93 93 72 c、对第2个节点进行调整 d、连续向下筛选

15 18 30 36 45 53 48 72 93 e、原始堆

图3.6 建立原始堆

第二步，15与93交换位置后，重新调整为堆，18为堆顶元素

93

30 18

36 45 53

15 72 93 18 36 30 48 72 45 53 48 93 15 30 36 30 72 45 53 48 图3.7 第二次调整

图3.8 第三次调整

36 48 72 45 53 93 18 15 18 15 3.6 折半插入排序

因为 R[1..i-1] 是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。如同直接插

入排序，只是确定插入的位置时，选择折半查找的方法。 7、简单选择排序

假设排序过程中，待排记录序列的状态为：

有序序列R[1..i-1] 无序序列 R[i..n] 图3.9 待排序记录序列

排序过程：

第i简单选择排序，从无序序列中选择最小的一个元素，插入到有序序列当中去。

有序序列R[1..i] 无序序列 R[i+1..n] 4 运行结果 图3.10 进行一趟简单选择排序后得序列

4 技术难点与分析

4.1 将四个子程序串成一个整体

解决方法：通过编写一个主程序 [4]

void main() { int i,k; char ch='y'; SqList *l;

l=(SqList *)malloc(sizeof(SqList )); while(ch=='y') { ……

InsertSort(l,m,n);

}

printf(\"\\n是否继续操作(y/n):\"); getchar(); ch=getchar(); }

}对四个子程序进行调用，始之构成一个整体。

4.2 如何对四个子程序的比较和移动次数进行定义

如果都采用整体变量，则在执行过程中会出现数据累加现象，导致计算结果出错，故在定义过程中部分采用整体变量，部分采用局部变量，以此来避免产生冲突。

整体变量执行一次之后的结果如图4.1所示：

……

BubbleSort(l,1,l->length); ……

子程序调用

QuickSort(l,1,l->length); …… HeapSort(l); ……

图4.1 采用整体变量执行一次

整体变量执行二次之后的结果如图4.2所示：出现数据累加现象

图4.2采用整体变量执行二次

整体和局部变量并用执行两次的结果如图4.3所示，无数据累加情况

图4.3 整体和局部变量并用执行两次

5系统测试

5.1 系统主界面

图5.1 系统主界面

5.2 直接插入排序测试

图5.2 直接插入排序测试

5.3 冒泡排序测试

图5.3 冒泡排序测试结果

5.4 快速选择排序测试

图5.4 快速选择排序测试结果

5.5 堆排序测试

图5.5 堆排序测试结果

5.6 折半插入排序

图5.6 折半插入排序测试结果

5.7 简单选择排序

图5.7 简单选择排序

6 结束语

数据结构课程设计和现代计算机技术的实际应用相结合，是我们在本学期学完理

论课程之后对自己学习能力的一次很好的检验，从开始的算法思路到运行调试后的可执行程序，都是一个很好的学习和锻炼的过程。既可以使我们巩固了原有的理论知识，培养了我们灵活运用和组合集成所学过知识及技能来分析、解决实际问题的能力，也可以使我们体会到自身知识和能力能在实际中的应用和发挥。不但可以激发创新意识，还可以开发创造能力、培养沟通能力。这次数据结构课程设计的时间里虽然时间有限，但确实使我受益非浅。通过实践课程设计我丰富了编译工具操作经验，更加深了对C语言的了解，熟悉了其环境，更增强了对排序算法的理解与运用。

而且，在完成本课程设计的过程中，也充满磨练了我的意志，锻炼了我的耐心、认真。在实践的过程中，需要不断的查阅资料，甚至需要求助于老师、同学。在课程设计中要善于思考，多动手。我深知，完成这样一项任务需要克服许多困难。

总之，数据结构课程设计让我受益良多，我会好好珍惜像这种难得的机会，努力学习知识。也感谢帮助了我的老师、同学。

参考文献

[1] 严蔚敏，吴伟民，数据结构（C语言版）.北京：清华大学出版社，1997 [2] 谭浩强，C程序设计（第三版）.北京：清华大学出版社，2005

[3] 谭浩强，C语言程序设计题解与上机指导(第三版).北京：清华大学出版社，2005 [4] Jeri R.Hanly，Elliot B. Koffman，问题求解与程序设计C语言版（第四版）.北京：清华大学出版社，2007-1

[5] 何钦铭，颜晖，C语言设计教程.北京:高等教育出版社，2008年 [6] 吴文虎，程序设计基础.北京:清华大学出版社，2003

附 录 ：系统源程序代码

#include #include #include

#define MaxSize 10 //顺序表的最大长度

typedef int KeyType; //定义关键字的类型为整数类型 typedef int InfoType; //定义其他类型为整数类型 int ptime=0;

int a=0,b=0,c=0,d=0; //置快速排序和堆排序的移动和比较次数 typedef struct {

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

}RedType;

typedef struct {

RedType r[MaxSize+1]; //r[0]作为监视哨 int length; //顺序表长度

}SqList;

void print(SqList *l) { }

//---------------------------------------------------------------------------------------------------------------int i;

for(i=1;i<=l->length;i++)

printf(\"%5d\

printf(\"\\n\");

----------------- //直接插入排序

void InsertSort(SqList *l,int m,int n)

{//对数组元素r[1]到r[l->length]中的n个元素进行直接插入排序 //r[0]中的内容不作为排序数据，作为一个标记又称为监视哨

int i,j;

for(i=2;i<=l->length;i++) //n-1次循环 {

l->r[0]=l->r[i]; //将需要插入的值r[i]赋值给]r[0],设置监

视哨 }

//-------------------------------------------------------------------------------------------------------------------------------- //冒泡排序

void BubbleSort(SqList *l,int m,int n) {

int i,j,k=0; }

printf(\"直接插入排序的移动次数为：%d,比较次数为：%d\\n\

j=i-1; m++;

while(l->r[0].keyr[j].key&&++n) //查找插入位置 { }

l->r[j+1]=l->r[0]; //将原r[i]中的记录存入第j+1个位置 printf(\"第%d趟排序结果为:\ print(l);

l->r[j+1]=l->r[j]; //前值覆盖后值 j--; m++;

RedType temp;

}

for(i=l->length;i>1;i--) //n-1趟比较 { }

printf(\"冒泡排序的移动次数为：%d,比较次数为：%d\\n\

for(j=1;jprintf(\"第%d趟排序结果为:\ print(l);

if(l->r[j].key>l->r[j+1].key&&++n) { }

temp=l->r[j]; //交换数据 l->r[j]=l->r[j+1]; l->r[j+1]=temp; m=m+3;

//-------------------------------------------------------------------------------------------------------------------------------- //快速排序

void QuickSort (SqList *l, int Left,int Right) {

int i,j,temp;

i=Left;j=Right;temp=l->r[i].key;//设置初始的排序区

//将i和j分别记录待排序区域的最左侧记录和最右侧记录的位置 while(iwhile (ir[j].key) //从右侧开始扫描

{

j--; b++;

} //找到第一个小于基准记录的数据

l->r[i]=l->r[j];//覆盖l->r[i]

a++;

while (ir[i].key<=temp) //从右侧开始扫描 {

i++;

b++; } //找到第一个大于基准记录的数据 l->r[j]=l->r[i]; //覆盖l->r[j] a++;

}

l->r[i].key=temp;//找到正确位置 a++; ptime++;

printf(\"第%d次划分排序为:\ print(l); if (LeftQuickSort(l,Left,i-1); //递归调用对左侧分区域再进行快速排序

if (i+1//-------------------------------------------------------------------------------------------------------------------------------- //堆排序

//调整l->r[x]的关键字使l->r[x...y]成为一个大堆 void HeapAdjust(SqList *l, int x,int y) {

int j;

QuickSort(l,i+1,Right); //递归调用对右侧分区域再进行快速排序

l->r[0]=l->r[x] ; for(j=2*x;j<=y;j=j*2) { if(jr[j].keyr[j+1].key)

++j;//j为key值较大的记录下标

d++;

if(l->r[0].key>l->r[j].key) { d++; break; }

l->r[x]=l->r[j]; c++; x=j;

}

l->r[x]=l->r[0]; c++;

}

//对顺序表l进行堆排序 void HeapSort(SqList *l) { int i,j;

for(i=l->length/2;i>=0;--i)

HeapAdjust(l,i,l->length);

printf(\"初始序列建成堆：\"); print(l);

for(j=l->length;j>1;--j) 趟 {

l->r[0]=l->r[j];

//将l->r[1...i]建成初始堆 //对当前l->r[1...i]进行堆排序，共做n-1

l->r[j]=l->r[1]; l->r[1]=l->r[0]; c=c+3;

HeapAdjust(l,1,j-1);

printf(\"第%d趟建堆结果为:\

print(l);

}

}

void BinSort (SqList *l, int length)

/*对记录数组r进行折半插入排序，length为数组的长度*/ { int i,j; RedType x; int low,high,mid;

for ( i=2; i<=length ; ++i ) { x=l-> r[i]; low=1; high=i-1;

while (low<=high ) /* 确定插入位置*/ { mid=(low+high) / 2;

if ( x.key r[mid].key )

high=mid-1;

else

low=mid+1;

}

for ( j=i-1 ; j>= low; --j ) l->r[j+1]= l->r[j]; /* */ l->r[low]=x; /* 插入记录 */

printf(\"第%d趟排序结果为:\ 记录依次向后移动

}

print(l);

}/*BinSort*/

void SelectSort(SqList *l, int length)

/*对记录数组r做简单选择排序，length为数组的长度*/ {

int i,j,k; int n; RedType x;

n=length;

for ( i=1 ; i<= n-1; ++i) { }

k=i;

for ( j=i+1 ; j<= n ; ++j)

if (l->r[j].key < l->r[k].key )

k=j;

if ( k!=i) { }

printf(\"第%d趟排序结果为:\

x= l->r[i]; l->r[i]= l->r[k]; l->r[k]=x;

print(l);

} /* SelectSort */

void main() {

int i,k; char ch='y'; SqList *l;

l=(SqList *)malloc(sizeof(SqList ));

while(ch=='y') {

int m=0,n=0; //置直接插入排序和冒泡排序的移动和比较次数 printf(\"\\n\\n\\n\");

printf(\"\\~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\n\");

printf(\"\\#*#*#*#*欢迎进入排序管理系统*#*#*#*#\\n\"); printf(\"\\~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\\n\"); printf(\"\\n\\n\\n\");

printf(\"如果碰到意外结束的情况或者排序不正确的情况，请及时联系管理员李

立强、\\n\\n\");

printf(\"本系统为免费系统，如带来任何问题，自己负责、\\n\\n\"); printf(\"\\★☆★☆欢迎使用排序管理系统☆★☆★\\n\");

printf(\"\\☆ 请选择所需功能: ☆\\n\");

printf(\"\\★ 1.直接插入排序 ★\\n\"); printf(\"\\☆ 2.冒泡排序 ☆\\n\"); printf(\"\\★ 3.快速排序 ★\\n\"); printf(\"\\☆ 4.堆排序 ☆\\n\"); printf(\"\\☆ 5.折半插入排序 ☆\\n\"); printf(\"\\☆ 6.简单选择排序 ☆\\n\"); printf(\"\\★ 7.退出系统 ★\\n\"); printf(\"\\☆★☆★欢迎使用排序管理系统★☆★☆\\n\"); printf(\"\\n\\n\\n\"); printf(\"请选择：\"); scanf(\"%d\

switch (k) {

case 1:printf(\"\\n您选择的是直接插入排序：\\n\");

printf(\"输入要排序列表的长度n：\");

scanf(\"%d\

for(i=1;i<=l->length;i++) {

printf(\"输入第%d个记录的关键字：\ scanf(\"%d\

}

printf(\"初始输入序列为：\"); print(l); InsertSort(l,m,n);

printf(\"直接插入排序后记录为:\"); print(l); break;

case 2:printf(\"\\n您选择的是冒泡排序：\\n\");

printf(\"输入要排序列表的长度n：\");

scanf(\"%d\

for(i=1;i<=l->length;i++) {

printf(\"输入第%d个记录的关键字：\ scanf(\"%d\

}

printf(\"初始输入序列为：\"); print(l);

BubbleSort(l,1,l->length); printf(\"冒泡排序后记录为：\"); print(l); break;

case 3:printf(\"\\n您选择的是快速排序：\\n\");

printf(\"输入要排序列表的长度n：\"); scanf(\"%d\ for(i=1;i<=l->length;i++) {

printf(\"输入第%d个记录的关键字：\ scanf(\"%d\ }

printf(\"初始输入序列为：\"); print(l);

QuickSort(l,1,l->length);

printf(\"快速排序的移动次数为：%d,比较次数为：%d\\n\ printf(\"快速排序后记录为:\"); print(l); break;

case 4:printf(\"\\n您选择的是堆排序：\\n\"); printf(\"输入要排序列表的长度n：\"); scanf(\"%d\ for(i=1;i<=l->length;i++) {

printf(\"输入第%d个记录的关键字：\ scanf(\"%d\ }

printf(\"初始输入序列为：\"); print(l); HeapSort(l);

printf(\"堆排序的移动次数为：%d,比较次数为：%d\\n\ printf(\"堆排序后记录为：\"); print(l); break;

case 5:printf(\"\\n您选择的是折半插入排序：\\n\"); printf(\"输入要排序列表的长度n：\");

scanf(\"%d\ for(i=1;i<=l->length;i++) {

printf(\"输入第%d个记录的关键字：\ scanf(\"%d\ }

printf(\"初始输入序列为：\"); print(l);

BinSort (l,l->length); printf(\"快速排序后记录为:\"); print(l); break;

case 6:printf(\"\\n您选择的是简单选择排序：\\n\"); printf(\"输入要排序列表的长度n：\"); scanf(\"%d\ for(i=1;i<=l->length;i++) {

printf(\"输入第%d个记录的关键字：\ scanf(\"%d\ }

printf(\"初始输入序列为：\"); print(l);

SelectSort(l, l->length); printf(\"快速排序后记录为:\"); print(l); break;

case 7:break;

default:printf(\"没有找到你需要的排序方法\"); break; }

printf(\"\\n是否继续操作(y/n):\");

getchar(); ch=getchar(); } }

致 谢

时间飞逝，大学的学习生活很快就要过去，在这四年的学习生活中，收获了很多，而这些成绩的取得是和一直关心帮助我的人分不开的。

首先非常感谢学校开设这个课题，为本人日后从事计算机方面的工作提供了经验，奠定了基础。本次毕业设计大概持续了半年，现在终于到结尾了。本次毕业设计是对我大学四年学习下来最好的检验。经过这次毕业设计，我的能力有了很大的提高，比如操作能力、分析问题的能力、合作精神、严谨的工作作风等方方面面都有很大的进步。这期间凝聚了很多人的心血，在此我表示由衷的感谢。没有他们的帮助，我将无法顺利完成这次设计。

首先，我要特别感谢我的知道郭谦功老师对我的悉心指导，在我的论文书写及设计过程中给了我大量的帮助和指导，为我理清了设计思路和操作方法，并对我所做的课题提出了有效的改进方案。郭谦功老师渊博的知识、严谨的作风和诲人不倦的态度给我留下了深刻的印象。从他身上，我学到了许多能受益终生的东西。再次对周巍老师表示衷心的感谢。

其次，我要感谢大学四年中所有的任课老师和辅导员在学习期间对我的严格要求，感谢他们对我学习上和生活上的帮助，使我了解了许多专业知识和为人的道理，能够在今后的生活道路上有继续奋斗的力量。

另外，我还要感谢大学四年和我一起走过的同学朋友对我的关心与支持，与他们一起学习、生活，让我在大学期间生活的很充实，给我留下了很多难忘的回忆。

最后，我要感谢我的父母对我的关系和理解，如果没有他们在我的学习生涯中的无私奉献和默默支持，我将无法顺利完成今天的学业。

致 谢

四年的大学生活就快走入尾声，我们的校园生活就要划上句号，心中是无尽的难舍与眷恋。从这里走出，对我的人生来说，将是踏上一个新的征程，要把所学的知识应用到实际工作中去。

回首四年，取得了些许成绩，生活中有快乐也有艰辛。感谢老师四年来对我孜孜不倦的教诲，对我成长的关心和爱护。

学友情深，情同兄妹。四年的风风雨雨，我们一同走过，充满着关爱，给我留下了值得珍藏的最美好的记忆。

在我的十几年求学历程里，离不开父母的鼓励和支持，是他们辛勤的劳作，无私的付出，为我创造良好的学习条件，我才能顺利完成完成学业，感激他们一直以来对我的抚养与培育。 最后，我要特别感谢我的导师刘望蜀老师、和研究生助教吴子仪老师。是他们在我毕业的最后关头给了我们巨大的帮助与鼓励，给了我很多解决问题的思路，在此表示衷心的感激。老师们认真负责的工作态度，严谨的治学精神和深厚的理论水平都使我收益匪浅。他无论在理论上还是在实践中，都给与我很大的帮助，使我得到不少的提高这对于我以后的工作和学习都有一种巨大的帮助，感谢他耐心的辅导。在论文的撰写过程中老师们给予我很大的帮助，帮助解决了不少的难点，使得论文能够及时完成，这里一并表示真诚的感谢。