《visual_c++_6.0_各种排序的算法_报告及源程序》由会员分享，可在线阅读，更多相关《visual_c++_6.0_各种排序的算法_报告及源程序（29页珍藏版）》请在金锄头文库上搜索。
1、1摘要近几年来，C 语言发展迅速，而且成为最受欢迎的语言之一，主要原因是它具有强大的功效，很多著名的系统软件就是由 C 语言编写出来的。它与汇编语言的结合，更体现出 C 语言的优越性。排序算法主要有直接插入排序，折半插入排序，希尔排序，冒泡排序，双向冒泡排序，快速排序，选择排序，堆排序，基数排序这几种。通过对各种排序方法的比较，我们能够很直观的发现各种排序方法的特点及各自的优缺点。此次课程设计主要挑选了选择排序、插入排序、冒泡排序这三种排序方法，通过对这三种排序方法的比较，希望能够让大家对一些排序方法有更加直观、深入的了解。设计中主要解决了用 time()、srand() 函数辅助 rand(
2、)函数随机产生了 0 到 99999 之间的数据；借助指针申请了动态内存解决了将同一随机数组的三次复制进而确保在相同随机数组的基础上三种比较算法的比较；在各种算法中运用 clock()函数计算完成比较所用的时间，并在各种比较算法的编程理解中完成比较、交换次数的计数；将随机数组写入文件等问题。关键词：随机数 排序 交换 时间 2目录1. 设计内容、设计参数及要求11.1 设计内容11.2 设计参数11.3 要求12. 总体设计思路22.1 设计系统的功能22.2 算法思想22.3 系统的总体框架332.4 系统的总体流程图43. 功能模块的具体设计53.1 main( )主函数53.2 Sele
3、ctSort( )函数73.3 InsertSort( )函数93.4 PopSort( )函数113.5 将随机数写入程序133.6 welcome( )函数144. 模块的调试及测试1545. 总结与个人体会175.1 总结175.2 个人体会176. 致谢197. 参考文献20附程序源代码2151. 设 计 内 容 和 要 求1.1 设计内容通过随机函数随机生成 100000 个数字，这些数字都是在0，99999之间。(2)并通过设计的排序算法进行排序。这些排序算法中包括冒泡法、选择法、插入法，也可以适当选择其他算法，但必须是较为典型的排序算法。(3)排序完毕后应给出相应的比较信息，其中
4、包括排序时间，比较次数和交换次数等信息。(4)在程序的主界面显示出最后的比较结论。(5)查看完比较结果后，即可点击回车退出系统1.2 设计参数(1)将排序前生成的 100000 个随机数存入一个文本文件中，该文件命名为BeforeSort.txt。(2)将排序好的数字分别按照不同的排序方式存入不同的文件中，冒泡法排序后的数字存入 PopSort.txt 中，选择法排序后的数字存入 SelectSort.txt 中，插入法排序后的数字存入 InsertSort.txt 中。1.3 要求1.3.1 基本要求精确测试上述三种排序方法对同样的数据进行排序所消耗的时间，比较次数以及交换次数，明确各种排序
5、的编写方法，分析各种排序方法在不同情况下的优劣。1.3.2 附加要求（1）程序启动后有较漂亮的封面页。(2 ) 结果以列表形式，较友好的人机界面显示62. 总 体 设 计 思 路2.1 设计系统的功能在“Before.txt” 中存储随机数。在”SelectSort.txt”、 ”InsertSort.txt”、 ”PopSort.txt”中存储经过排序后的有序数列。通过对主界面中三种排序方法所用时间、比较次数、交换次数等信息的观察，了解到各自排序方法的特点及优劣。2.2 算法思路2.1.1 选择排序为了便于理解，设有 10 个数分别存在数组元素 a0a9中。选择排序法是由大到小依次定位 a0
6、a9中恰当的值，a9 中放的自然是最小的数。如定位 a0,先假定 a0中当前值是最大数，a0与后面的元素一一比较，如果 a4更大，则将 a0、a4交换，a0已更新再与后面的 a5a9 比较，如果 a8还要大，则将 a0、a8交换，a0 又是新数，再与 a9比较。一轮比完以后，a0 就是最大的数了，本次比武的武状元诞生了，接下来从 a1开始，再来一轮 a1就是次大的数，然后从 a2开始，当比到 a8以后，排序就完成了。2.2.2 插入排序每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序，直到待排序数据元素全部插入完为止。即经过 i-1 遍处后,L1.i-1己排好
7、序。第 i 遍处理仅将 L 插入 L1.i-1的适当位置 p，原来 p 后的元素一一向右移动一个位置,使得 L1.i又是排好序的序列。72.2.3 冒泡排序首先将第一个记录的随机数和第二个记录的随机数进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的随机数。依此类推，直到第 N-1 和第 N 个记录的随机数进行过比较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序，对前 N-1 个记录进行同样操作。一共要进行 N-1 趟起泡排序2.3 系统的总体框架图登录选择排序 插入排序 冒泡排序将排序结果放入文件将排序结果放入文件
8、将排序结果放入文件结束主函数退出82.4 系统的总体流程图调用随机数函数，产生 10000 个随机数打开一个“BeforeSort.txt”文本文档，将这 10000 个随机数放到文本文档中选择排序，并得出其时间消耗，比较次数，交换次数插入排序，并得出其时间消耗，比较次数，交换次数冒泡排序，并得出其时间消耗，比较次数，交换次数将经过选择排序好的 10000 个数字存放到“SelectSort.txt”文本文档将经过插入排序好的 10000 个数字存放到“InsertSort.txt”文本文档将经过排序好的10000 个数字存放到“PopSort.txt”文本文档程序结束退出进入登录界面按“En
9、ter”键进入主界面93.功能模块的具体设计3.1 main( ) 主函数主函数功能比较简单，用 srand( (unsigned)time( NULL ) )语句以及 for 循环语句产生随机数。打开BeforeSort.txt文本文档，将随机数放入该文本文档中。使用动态内存，定义选择、插入、冒泡三种排序方法。在主函数的前面要写必须的头文件，预定义语句。3.1.1 随机函数的产生函数 rand()将产生一个在 0 到 RAND_MAX 之间的整数，其中 RAND_MAX 是头文件中定义的一个符号常量，并且至少是 32767，即 16 位二进制数所能表示的最大整数。并可以利用比例缩放（求余运算
10、）产生一系列 0 到所需数（小于RAND_MAX）之间的数 。但实际操作中最大只能得到 0 到 10000 之间的数，所以采用了分别获取 0 到 10000 之间的数加上 0 到 10 之间的数最终得到 0 到 100000 之间的数的方法。但是 rand()函数具有重复性，并且这种重复性可用于验证该函数运行正确与否，故要借助 srand()、time()对该函数进行随机化。其中，函数 time 的返回值是以秒为单位的从 1970 年 1 月 1 日午夜开始到现在所经历的时间，time 函数的返回值被转换成一个无符号的种子传递给 srand()函数以产生随机数表 3.1.1 随机数的产生中间变
11、量Ri = ka= rand()%10000b = a*10c = rand()%10k = b+cR 0 5465R1 723R2 8421R3 69R4 362310 i = 0i #includevoid main()clock_t start;11clock_t end;int t;long i;start=clock(); /得到程序运行时的时间量的值for(i=0;i=0;j-) cpt2+;if(temp=Rj)break;Rj+1=Rj;Rj+1=temp;if(j+1=i-1)count2+;else count2=count2+0;14i = 1i = 0break是真 假
12、图 3.3.1 插入排序流程图153.4 Popsort（）函数利用 for 循环语句，对“BeforeSort.txt “中的随机数进行选择排序，并打开“PoptSort.txt”文本文档，将经过冒泡排序的数放入该文本文档。用 clock-start 及 clock-end 语句计算出冒泡排序所用的时间，用 for 循环语句得出比较次数和交换次数。用printf 将冒泡排序时间，比较次数以及交换次数这些信息在主界面中输出。3.4.1 冒泡排序程序void PopSort(int R ,int n) /*冒泡排序*/ int i,j,t;double count3=0.0, cpt4=0.0; FILE*fp;clock_t start;clock_t end;double time3;start=clock(); for(i=1;iRj+1)count3+;
