常用排序算法的比较

更新时间：2023-03-20 08:44:01 阅读量：实用文档文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

0。0 第一次写了10KB+的代码略感动。虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

重庆科技学院

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

学院: 电气与信息工程学院专业班级: 计科2012 学生姓名: 马赛克学号: 马赛克设计地点（单位）计算机基础自主学习中心

设计题目: 常用排序算法的比较完成日期： 2013 年 7 月 12 日

指导教师评语:

______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

成绩（五级记分制）: ____________________

指导教师（签字）: _______________________

0。0 第一次写了10KB+的代码略感动。虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

重庆科技学院课程设计任务书

设计题目：常用排序算法的比较

系主任：易军指导教师：向毅/黄永文

2013年 6月 20日

0。0 第一次写了10KB+的代码略感动。虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

摘要

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素和集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率，处理各种问题。

该程序是用C语言编写的，它充分体现数据结构的理念与算法的魅力。该程序植入多种排序方法，这些排序方法的算法各具有特色，利用多种算法达到同一效果，正所谓“条条大路通罗马”。并且，该程序还收集各算法的运行时间，通过对耗时的比较，为用户挑选出两种最优化的排序方法。

关键字：排序逻辑运算数据结构时间复杂度

0。0 第一次写了10KB+的代码略感动。虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

摘要 ............................................................................................................................. II 目录 .............................................................................................................................. III 1.需求分析 ..................................................................................................................... 1

1.1问题描述 ........................................................................................................... 1 1.2基本要求和目的 ............................................................................................... 1 2. 程序设计 ................................................................................................................... 2

2.1 概述 .................................................................................................................. 2 2.2程序运行流程图 ............................................................................................... 2 2.3主要算法的具体逻辑分析 ............................................................................... 2 2.3主要算法的具体逻辑分析 ............................................................................... 3

2.3.1直接插入排序 ......................................................................................... 3 2.3.2折半查找插入排序 ................................................................................. 3 2.3.3希尔排序 ................................................................................................. 4 2.3.4冒泡排序. ................................................................................................ 5 2.3.5快速排序 ................................................................................................. 5 2.3.6简单选择排序 ......................................................................................... 7 2.3.7堆排序 ..................................................................................................... 7 2.3.8 归并排序 ................................................................................................ 8

3. 程序测试 ................................................................................................................. 10

3.1 运行的主界面 ................................................................................................ 10 3.2随机数的产生 ................................................................................................. 10 3.3 排序完成界面 ................................................................................................ 11 3.4 进入菜单 ........................................................................................................ 12 3.5 按照菜单提示操作 ........................................................................................ 13 4. 总结 ......................................................................................................................... 15 参考文献 ...................................................................................................................... 28

0。0 第一次写了10KB+的代码略感动。虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

1.需求分析

1.1问题描述

排序是计算机程序设计中的一项重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个相值有序的序列。

排序在现实生活中具有广泛的应用，如电话簿的按姓名排序，帮助快速查找联系人；考试成绩的排序能够定位知识技能掌握更好的人，帮助公司挑选人才；比赛成绩的排序帮助了解选手平时训练的程度和参加比赛时发挥的状态；公司业绩的排序帮助管理人员掌握谁更努力工作，给公司创造了更大的效益。因此，学习排序算法，对排序进行研究、实践，能够很好的帮助我们练习。

1.2基本要求和目的

基本要求：随机产生100000个随机数，利用编写的排序法，分别实现对这些随机数的排序整合，计算各自运行的时间，并将排好的有序序列和运算耗时输入到各自对应的文件中。

目的： 1.

巩固和加深学生对数据结构算法的理解，提高综合运用所学课程知识的能力； 2.

通过各个排序算法的实现，练习包括文件的读写、动态内存的申请、函数的应用、指针的应用等多种最基本的C语言操作； 3.

锻炼学生的动手能力与培养其独立思考的能力。

0。0 第一次写了10KB+的代码略感动。虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

2.程序设计

2.1 概述

该程序用typedef struct_Time{ Char Name[20]; // 算法名称 Double Num;//运算所需时间 }Time;

利用结构体Time储存排序算法名称，以及算法排序所用具体时间。这样的定义，方便了在比较时间长短时，能够对应的知道算法名称。从而更方便的判断哪种算法比较优化。

在具体运算中，该程序代码的具体功能如下： GetRandom（）：按照用户的需要，输入所需测试的随机数个数，产生随机数至文件里；

rRandom（）：利用文件指针，将文件里的数据读写到程序里利用指针申请的动态内存当中；

InsertSort（）：直接插入排序； BinarySort（）：折半查找插入排序； ShellSort（）：希尔排序； BubbleSort（）：冒泡排序； QuickSort（）：快速排序； SelectSort（）：简单选择排序； HeapSort（）：堆排序； MergeSort（）：归并排序； Fprintf（）：将排序好的数据记录到文件当中； TimeSort（）：利用Time的指针，对存入Time的动态内存中的元素的关键字Num进行排序，找出耗时最短时间的两种排序方法；

IntoMenu（）：程序人性化体现，按照菜单提示轻松使用该程序。

2.2程序运行流程图

0。0 第一次写了10KB+的代码略感动。虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

2.3主要算法的具体逻辑分析

2.3.1直接插入排序

直接插入排序的主要思路是，将待排序的数值不断的插入到有序段中，将有序段逐渐扩大，知道所有数值进入有序段中。

InsertSort（）：

for( i = 1; i <= Num; i++) { p[0] = p[i]; j = i -1; while( p[0] < p[j]) { p[j +1] = p[j];//将大于p[i]的数往后移动 j--; } p[j +1] = p[0]; }

亮点：将顺序表中的p[0]（第一个元素）作为排序的哨兵，不用于存储有效数据，用来保存第i个元素p[i]的副本，使不导致因为记录后移而丢失p[i]的内容。还在查找循环中“监视”下标变量j是否越界。防止数据溢出造成错误。

2.3.2折半查找插入排序

该方法，在直接插入排序的思路之上，将查找方式——折半查找植入到算法当中。

折半查找，先取有序段的中间元素与查找值进行比较。如查找值小于中间元素，则再取低半部的中间元素与查找值进行比较。如此重复知道查找成功或最终未找到这个数为止。

与直接插入排序法相比，折半查找排序法减少了与关键字相比较的次数，从而提高了算法的效率。

BinarySort（）：

for( i = 1; i <= Num; i++) { p[0] = p[i]; low = 1; high = i -1; while(low <= high)//寻找有序列中待插入值的位置 { m = (low + high)/2; if(p[0] < p[m])

0。0 第一次写了10KB+的代码略感动。虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

high = m-1; else low = m +1; } for( j = i-1; j > high ; j--)//将找到的待插入值应在的位置腾出（往后移动其他数据） { p[j+1] = p[j]; } p[high +1] = p[0];//插入值 }

代码中，有外层for循环负责Num – 1次扫描，完成寻找序列中所有记录的插入位置，内层的while循环就是通过折半查找的方法定位当前元素在有序段中的位置。为了把当前元素复制到有序断种，需要把大于当前元素关键字的元素往后移动，内层的for循环就是移动大于当前元素关键字的元素，最后在外循环里将当前元素的值插入到正确位置。

2.3.3希尔排序

希尔排序是对直接插入排序算法的改进，通过减少元素的移动来优化算法，提高算法的效率。其基本思想是，将待排序的记录分成几组，每组中元素都比原来的序列少，从而减少参与直接插入排序的数据量，在各组中分别进行直接插入排序。通过几次排序之后，记录的排列已经基本上有序，这时候再对所有的记录实施直接插入排序。

ShellSort（）：

for( d = (Num+1) / 2; d >= 1; d = d/2) //设置排序的步长d，每次步长减半，直到减到1

{ for( i = d+1; i <= Num; i++)//定位到每个元素 { p[0] = p[i]; j = i - d; while( j > 0 && p[0] < p[j]) { p[j +d] = p[j]; j = j - d; } p[j + d] = p[0]; } }

具体步骤描述：待排序的记录为Num个，先选取整数 d (d<n),将所有距离为d的记录构成一组，从而将整个待排序记录序列分割成为d个子序列，对每个分组分别进行直接插入排序，然后再缩小间隔d至d的一半，重复上述的步骤，直到最后取d = 1，即将所有记录放在一组进行最后一次直接插入排序，最终将

0。0 第一次写了10KB+的代码略感动。虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

所有记录重新排列成关键字有序的序列。

2.3.4冒泡排序.

冒泡排序的基本思想就是将待排序的元素看作是竖着排列的“气泡”，关键字较小的元素比较轻，从而要往上浮。在冒泡排序算法中需要对这个“气泡”序列处理若干遍。处理方法为，自底而上检查一遍整个序列，并时刻注意两个相邻元素的顺序是否正确。如果发现两个相邻元素逆序，即“轻”的元素如果在下边，就交换它们的位置。这样处理一遍之后，“最轻”的元素浮到了第一个，处理第二遍之后“次轻”的元素就浮到了第二个位置。并且，在作第二遍处理的时候，由于第一个位置上的元素已经是“最轻”，所以不必再次比较。即，第i遍处理时，不必检查第i个位置以下的元素。

BubbleSort（）：

for( i = Num; i >= 1; i--) { for( j = Num; j > swap; j--) { if(p[j] < p[j -1])//如果“轻”的元素在下边，则将其与上一个元素交换位置

{ p[0] = p[j -1]; p[j - 1] = p[j]; p[j] = p[0]; } } swap++;//监控排序次数 }

基本过程和算法：

第一遍冒泡排序，首先第Num个元素与第Num – 1个元素比较，逆序则交换；然后第Num -1元素与第Num – 1个元素比较；直到第二个元素与第一个元素比较为止。结果，关键字最小的元素放在第一的位置。

第二遍冒泡排序，除了对第一个之外的Num -1个元素进行相同操作，结果次小元素放在第二的位置上。

在排序过程中监控比较次数，当比较次数为 temp为 Num -1时，排序过程结束，所有元素都已经有序。

2.3.5快速排序

快速排序的基本思想是，通过一轮排序将序列分割成独立的两部分，其中一部分序列的关键字均比另一部分关键字小。继对长度缩短的序列进行同样的分

0。0 第一次写了10KB+的代码略感动。虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

割，最后达到整体有序。在排序过程中，由于已经分开的两部分的元素不再需要进行比较，所以减少了比较次数，提高了排序效率，降低了排序时间。

QuickSort（）： temp = p[x]; while( i < j) { while((p[j] >= temp)&&(j > i))//j向前搜索，寻找关键字小于基准值的位置

{ j--; } if(j > i) { p[i] = p[j]; i++; while((p[i] <= temp) && ( i < j))//i 向后搜索，寻找关键字大于基准值的位置

{ i++; } if( i < j) { p[j] = p[i]; j--; } } }

p[i] = temp; if( i- 1 > x) QuickSort(p, x, i-1); if( j+1 < y) QuickSort(p, j+1, y);

首先，在序列p中选取一个中轴值p[x]，而后将p分开成为两个部分，其中左边的部分中的元素均小于或者等于p[x]，右边部分的元素均大于或等于中轴值，而后通过递归调用快速排序的过程分别对这两个部分进行排序，最后将这两个部分产生的结果合并即可得到最后的排序序列。

关于“基准值”，我使用的是第一个记录的关键字值。数组中待排序的记录中有j个记录的关键字小于基准值，这些记录就放在数组的最左边的k个位置（不包括p[0]）上，而大于基准值的记录就放在数组最右边的Num –j个位置上。基准值的位置的下标就是j。第一次划分之后，再用相同的算法对“基准值”左右子序列分别进行类似的操作，其中一个子序列有j个记录，另一个子序列有Num -（k+1）个记录。依此递归执行，知道每个子序列中的记录个数不超过一个为止，排序过程结束。

基本过程与算法：

首先选第一个记录作为枢轴附设两个指针i和j分别指向第一个记录和最后一个记录。

0。0 第一次写了10KB+的代码略感动。虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

指针j向前搜索逐个记录与基准值进行比较，直到发现小于基准值的记录为止，将其与枢轴记录相互交换。

指针i向后搜索逐个记录与基准值进行比较，直到发现大于基准值的记录为止，将其与枢轴记录相互交换。

重复上述步骤直到 i = j为止。完成一轮排序，完成一次分割，对前后两个子表按上述原则再分割，知道所有子表的表长不超过1为止。

2.3.6简单选择排序

简单选择排序的基本思想是，首先从序列中选出关键字最小的记录送到最前位置，再从余下的序列中选取关键字最小的记录送到第二的位置，直至寻列中所有的记录都已经选择为止。

SelectSort()：

for( i = 1; i <= Num; i++) { min = i; for( j = Num; j > i; j--) { if(p[min] > p[j]) min = j; } p[0] = p[min];//利用p[0]中介交换 p[min] = p[i]; p[i] = p[0]; }

算法：对数组p[]，将其从小到大进行排序，首先从p[1],p[2],p[3], ,p[Num]中选择最小值，找到之后，则将它的值与p[1]对换(借助p[0])；然后从p[2],p[3],p[4], ,p[Num]中选择最小值，再将其与p[2]对换。如此进行选择和调换，对第i趟选择排序，进行Num – 1次关键字比较，从Num –i +1个记录中选出关键字最小的记录，并与第i个记录交换。令i从1 至Num-1，进行Num-1趟选择排序，有序序列就此形成。

2.3.7堆排序

堆排序是一种基于选择排序的排序方法。它是一种树形选择排序，利用堆顶记录的关键字最小这一特征，使得在当前无序区中选取最大关键字的记录变得简单。

对任意的p[i（i = 1，2，3 ）]都有p[i] >= p[2 *i]并且p[i] >= p[2*i+1]。它的基本思想是，首先将待排序的记录序列构造成一个堆。此时，选出了堆中所有记录的最小值，然后将它从堆中移走，并将剩余的记录再调整成堆，又找

0。0 第一次写了10KB+的代码略感动。虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

次小的记录，依此类推，直到堆中最后只有一个记录位置，得到有序序列。

HeapSort（）

for (i = n/2; i >= 1; i --) sift(p , i , n); for (i = n; i > 1; i --) { temp = p[1]; p[1] = p[i]; p[i] = temp; sift(p, 1 , i - 1); }

Sift（）//筛选 temp = p[i]; j = 2 * i;

while (j <= m) {

if (j < m && p[j] < p[j+1]) { j ++; }

if (temp < p[j]) { p[i] = p[j]; i = j; j = 2 * i; }

else break; }

p[i] = temp;

算法：当前要进行筛选的节点编号为m ，堆中最后一个结点的编号为n,且p[m+1]至p[Num]之间的结点都已经满足堆的条件，则调整过程（函数Sift的功能）可以描述为：

（1）设置两个指针i和j：

i指向当前的结点； j指向当前节点的左孩子结点（2*i）

（2）比较当前结点的左右孩子的关键字的值，并用j指向关键字值较大的

孩子结点。

（3）用当前结点的关键字与j所指向的结点关键字的值进行比较，根据比

较结果采

取相应的操作，即结束筛选或交换结点内容并继续进行筛选。

2.3.8 归并排序

归并排序的基本思想是：将待排序文件堪称为Num个长度为1的有序子文件，把这些子文件两两归并，使得[Num/2]个长度为2的有序子文件；然后再把

0。0 第一次写了10KB+的代码略感动。虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

这个[Num/2]个有序文件的子文件两两归并，如此反复，直到最后得到一个长度为Num的有序文件为止。

MergeSort（） while(len < Num) { MergePass(p, len, Num); len *= 2; }

MergePass

for( i = 1; i+ 2*len-1 <= Num; i = i + 2* len) { Merge( p, i, i+len-1, i+ 2* len -1); }

if( i+ len -1 < Num)//尚有两个子文件，其中最后一个长度小于len { Merge( p, i, i+len-1, Num); }

Merge（） i = low;

j = m +1; k = 0;

q = (int *)malloc(sizeof(int) * high); while( i <= m && j <= high) { q[k++] = p[i] <= p[j]?p[i++]: p[j++]; }

while( i <= m) { q[k++] = p[i++];//将p[low m]中剩余的复制到q中 }

while( j<= high) { q[k++] = p[j++];///将p[m+k high]中剩余的复制到q中 }

for( k = 0, i = low; i<= high; k++, i++) { p[i] = q[k]; //

}//ps：q为p相同类型的指针

算法：在某趟归并中，设各子文件长度为len，则归并前p[1 n]中有[Num/len]个有序子文件。调用递归并操作对子文件进行归并时，必须对子文件的个数可能是奇数、最后一个子文件的长度可能小于len这两种特殊情况进行处理：若子文件个数为奇数，则最后一个子文件无须与其他子文件归并；若子文件个数为偶数，则要注意最后一对子文件中后一个子文件的区间上限为Num。（MergePass）

0。0 第一次写了10KB+的代码略感动。虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

重庆科技学院

数据结构课程设计报告

3.程序测试

3.1 运行的主界面

该程序运行的主界面如下（图3-1）：

图3.1 主界面

3.2随机数的产生

输入所需排列的随机数的个数，即可产生对应个数的随机数在当前文件 Random文件，执行后的界面如下（图3.1）：

0。0 第一次写了10KB+的代码略感动。虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

图3.2 随机数产生界面

3.3 排序完成界面

随机数产生后，程序将自动运行排序部分，排序完成后，界面如下（图3.3）：

、图3.3 排序完成

0。0 第一次写了10KB+的代码略感动。虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

3.4 进入菜单

按照如图3.3提示，进入菜单输入“1”，否则输入“0”退出。输入出错的的情况（图3.4）：

图 3.4 输入错误界面

正确进入菜单界面：（图3.5）

图 3.5 进入菜单

0。0 第一次写了10KB+的代码略感动。虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

3.5 按照菜单提示操作

按照菜单提示，可有四种情况出现。情况一：输入“1”，运行功能1（如图3.6）

图3.6 运行功能1

情况二：输入“2”，运行功能2（如图3.7）

图 3.7 运行功能2

0。0 第一次写了10KB+的代码略感动。虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

重庆科技学院

数据结构课程设计报告

情况三：输入错误（图3.8）

图3.8 输入错误

情况四：退出程序运行（如图3.9）

图 3.9 退出程序

0。0 第一次写了10KB+的代码略感动。虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

4. 总结

在为期两周的课程设计里，我基本上能够算得上是全面接触排序算法。刚开始拿到题目的时候，是完全无从下手的迷茫状态，之后通过自己的分析、资料的帮助和同学老师的帮助对排序的认识便逐渐的清晰起来。各个算法的逻辑算法我都很喜欢。毕竟是前人总结下来的经验，我只是很多年之后的经验运用而已。但我确实已经被这些算法所折服。

在效率方面，我也颇有感触。完成程序的第二天上午，我带着好奇准备用1000000个随机数来进行测试。从大概九点开始，一直运行到放学之后的十二点半以后。在程序运行完之前，因为必须得离开实验室的原因，当时的我既紧张又有一点小兴奋，忐忑的看着黑屏上的光标一直在跳动，可结果就是迟迟不出来。终于在我等待良久之后，结果运行出来。虽然本身是很无聊的一件事，但对我来说确实历史性的大事件。测试结果如下图。

看着这些时间长度的对比，我顿时产生了颇多感触。运行时间最长的四千多秒，与运行最短的少于一秒对比起来，这就是效率最明了的体现。以小见大，平时做事也要特别注意效率问题。

在编程中遇到了众多困难，很多时候并不是迎刃而解，尤其是在遇到逻辑错误的时候，常常会感觉到头昏脑胀，思维一片混乱。

有时候一两个小时都解决不

0。0 第一次写了10KB+的代码略感动。虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

了某个问题。通过这次实训，我深刻的体会到在遇到困难时，绝对得保持一颗清晰的头脑，不要着急，更不要恼怒。平心静气，一步一步慢慢分析会让效果提升很多。听说有一种名为“Rubber duck debugging（小黄鸭调试法）”，有机会一定要试用一下。

另一方面，完成这个任务，那种通过努力之后的成就感，也激发了我对编程的更多热爱。

在未来的编程之路上，我又将会不断的提升自己，又会获得更多宝贵的经验。即使遇到挫折又如何。真是期待啊。

0。0 第一次写了10KB+的代码略感动。虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

致谢

再强的一个人如果没有其他人的帮助，我相信他也不能在成功的道路上走得更远。

每次写复杂一些的编程，我便很想用“编程血泪史”来为我的道路做个深刻的标记。

在被编程错误困扰到的时候，谢谢同学和老师耐心的为我解答，为我调试找错，让我思路清晰化。