几种常见排序方法的比较

《几种常见排序方法的比较》由会员分享，可在线阅读，更多相关《几种常见排序方法的比较（13页珍藏版）》请在金锄头文库上搜索。

1、重庆邮电大学移通学院重庆邮电大学移通学院计算机软件技术基础计算机软件技术基础课程报告课程报告题题 目目 几种常见排序方法的比较几种常见排序方法的比较 姓姓 名名 谢枞谢枞 学学 号号 0111100320 班班 级级 01111003 专专 业业 通信工程通信工程 2012 年年 6 月月 4 日日摘 要该程序是用 C+语言实现的，在程序中随机生成 N 个数据，对这些数进行多种方法的排序，所用的这些排序方法都是在数据结构课中学习过的比如：插入排序、快速排序、冒泡排序等，而且还要对各个排序做出相应的比较。该演示程序以用户和计算机的对话方式执行，每次测试完毕，列表显示各种比较指标值。最后对结果作出

2、了简单分析并将结果排序，包括对各组数据得出结果波动大小给予解析。关键字：插入排序、冒泡排序、比较的个数、改变的个数、所用的时间。目目 录录摘要目录1问题描问题描述述11.1题目内容11.2基本要求11.3测试数据12需求分需求分析析22.1输入输出的形式和输入值的范围22.2程序所能达到的功能23概要设概要设计计33.1程序所需的抽象数据类型33.2系统功能模块33.2.1外部功能模块图 33.2.2主函数功能模块图34详细设详细设计计44.1 整个程序的流程图44.2 插入排序及其主要代码54.3 二路合并排序及其主要代码64.4 冒泡排序及其主要代码75 调试分调试分析析85.1 调试分析

3、结果96 总总结结101 问题描述1.1 题目内容本演示程序对以下几种常用的内部排序算法进行实测比较：起泡排序、直接插入排序、二路合并排序。主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性，如：正序、逆序和不同程度的乱序。注意采用分块调试的方法。1.2 基本要求1 待排序表的表长不小于 100，其中数据要用的随机数产生程序产生，至少要用 5 组不同的输入数据体比较，比较的指标为：有关键字参加的比较次数和关键字的移动次数（关键字交换计为 3 次的移动） 。2 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”下，用

4、户可由键盘输入待排序表的表长和不同的测试数据的数组，每次测试完毕，列表显示各种比较指标值。3最后对结果作出简单分析，包括对各组数据得出结果波动大小给予解析。1.3 测试数据由函数 rand 随机产生的数据。 2 2 需求分析需求分析2.1 输入输出的形式和输入值的范围由于程序中所需的数据都是有函数随机生成的整形数，不需要用户自己输入，用户只需要对演示程序中的一些提示做一些必要的选择以便于程序的执行。程序输出的是对五种排序做的一些比较，即输出五种排序各排序过程中所比较的数据的个数，交换的数据的次数，和排序完成所用的时间。六种排序依次在计算机终端上显示，便于用户观察。输入值的范围等价于程序中随机生

5、成的数据的个数，即待排序表的表长不小于 100，至少要用 5 组不同的输入数据体比较，比较的指标为：有关键字参加的比较次数和关键字的移动次数（关键字交换计为 3 次的移动） ，在该程序中，随机生成的数据个数被初始化为了 10000，数据越大就越容易比较。2.2 程序所能达到的功能输入 N 个随机整数，对这些数进行多种方法进行排序，并对这些排序做比较，在屏幕上输出每种排序方法所比较的次数，交换的次数，和用掉的时间。任意性：系统首先生成 10000 个随机整数，然后分别用不同的排序方法对其进行升序排序，给出每种方法的比较次数或所用时间友好性：界面要友好，输入有提示，尽量展示人性化可读性：源程序代码

6、清晰、有层次 健壮性：用户输入非法数据时，系统要及时给出警告信息3 概要设计3.1 程序所需的抽象数据类型typedef struct StudentData int num; /存放关键字，如零时变量，还有哨兵 Data;typedef struct LinkList int Length; /存放随机数的个数 Data RecordMAXSIZE;/用数组存放所有的随机数 LinkList;3.2 系统功能模块3.2.1 主函数功能模块图图 3.2.2 主函数功能模块图主函数 main（）set 定义或 初始化 变量InitLink List(Lin kList* L) 初始化 链表Sho

7、w the menu 显示主 界面Compare 比较六 种排序Display 把数据 写入文 件4.1 整个程序的流程图开始界面Compare 比较各排序插 入 排 序二路 合并 排序冒 泡 排 序比较各排序输出数据4.2 插入排序及其主要代码插入排序及其主要代码直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，它的基本操作是将一个纪录插入到已排好序的有序表中，从而得到一个新的、纪录数增 1 的有序表。例如，已知待排序的一组纪录的初始排列如下所示：R(49)、R(38)、R(65)、R(97)、R(76)、R(13)、R(27)、R(49) （4-1）假设

8、在排序过程中，前 4 个记录已按关键字递增的次序重新排列，构成一个含4 个纪录的有序序列 R(38)、R(49)、R(65)、R(97) （4-2） 现要将式（4-1）中的第 5 个纪录插入上述序列，以得到一个新的含 5个纪录的有序序列，则首先要在式（4-2）的序列中进行查找以确定 R(76)、所应插入的位置，然后进行插入。假设从 R(97)、起向左进行顺序查找，由于65Length;i+) if( LT(L-Recordi.num, L-Recordi-dk.num, CmpNum) ) memcpy( for(j=i-dk; j=0 j-=dk) (*ChgNum)+; (*ChgNum)

9、+; memcpy( memcpy( 4.3 二路合并排序及其主要代码二路合并排序及其主要代码二路合并排序是另一类时间复杂度为 O(nlog2n)的排序方法，它的基本思想 是：将有 n 个元素的序列看成是 n 个长度为 1 的有序子序列，然后两两合并子 序列，得到【n/2】个长度为 2 或 1 的有序子序列；再两两合并，直到得到 一个长度为 n 的有序子序列时结束，如图所示。template void Merge(T A,int i1,int j1,int i2,int j2) / i1,j1 是子序列 1 的下、上界，i1,j2 是子序列 2 的下、上界T *Temp=new Tj2-i1+

10、1; /分配能存放两个子序列的临时数组int i=i1,j=i2,k=0; /i,j 是两个子序列的游动指针，k 是 Temp 的游动指针while (i void MergeSort(T A, int n) int i1,j1,i2,j2; /i1,j1 是子序列 1 的下、上界，i2,j2 是子序列 2 的下、上界int size=1; /子序列中元素个数，初始化为 1。while (sizen-1) j2=n-1; /若第 2 个子序列中不足 size 个元素，则置子序列 2 的上界 j2=n-1else j2=i2+size-1; /否则有 size 个，置 j2=i2+size-1M

11、erge(A,i1,j1,i2,j2); /合并相邻两个子序列i1=j2+1; /确定下一次合并第一个子序列的下界 size*=2; /元素个数扩大一倍 程序只将 A 数组中相邻的两个子序列（Ai1,Ai1+1,.,Aj1）和(Ai2, Ai2+1,.,Aj2)合并为一个子序列，其中 i1、ji 是子序列 1 在数组 A 中的 下标，表示子序列的下、上界（i2Recordj.num,L-Recordj+1.num,CmpNum) (*ChgNum)+; memcpy( memcpy( memcpy( 6 总 结这次课程设计运用到了 c+语言和数据结构知识点，课设题目要求不仅要求对课本知识有较深

12、刻的了解，同时要求程序设计者有较强的思维和动手能力。这次课设使我了解我编程思想和编程技巧，也认识了软件生命周期的各个环境，包括构思、设计、编写、调试、发布、文档化、维护和修订。编程的风格也很重要，同学只关心程序运行的结果，而对程序代码的结构的良好丝毫不在意。这是非常不可取的，如果我们希望将来从事编程工作，在这一点上该引起足够的重视。这是严谨的态度，很重要！在写程序的过程中遇到的麻烦不是很多，由于课本上都把最基本的算法写的很清楚，我们只需要去理解，把分散的知识聚拢来，用学过的知识把一个一个的排序恰当的连接起来就能把程序的主要部分写好，再加一修改就可以了，而且在这一学期的学习生活中，我们已经把大多数的排序都写好了，所以这对于我们来说还是比较轻松的一件事，但是在写程序的过程中还是会遇到一些麻烦，那就需要我们的小心谨慎和积极探索的精神了，争取把程序写的更完美。做课程设计不仅让我修补了以前学习的漏洞，也让我知道一个道理：编程需要兴趣和实际动手。这应该可以借鉴在老师的教学工作上。创新思维至关重要，这不仅能让我们写出精简的代码，也有助于开发出高效的程序。