visual_c++_6.0_各种排序的算法_报告及源程序 本文关键词：源程序，算法，排序，报告，visual_c
visual_c++_6.0_各种排序的算法_报告及源程序 本文简介：摘要近几年来，C语言发展迅速，而且成为最受欢迎的语言之一，主要原因是它具有强大的功效，很多著名的系统软件就是由C语言编写出来的。它与汇编语言的结合，更体现出C语言的优越性。排序算法主要有直接插入排序，折半插入排序，希尔排序，冒泡排序，双向冒泡排序，快速排序，选择排序，堆排序，基数排序这几种。通过对各
visual_c++_6.0_各种排序的算法_报告及源程序 本文内容：
摘要
近几年来，C语言发展迅速，而且成为最受欢迎的语言之一，主要原因是它具有强大的功效，很多著名的系统软件就是由C语言编写出来的。它与汇编语言的结合，更体现出C语言的优越性。
排序算法主要有直接插入排序，折半插入排序，希尔排序，冒泡排序，双向冒泡排序，快速排序，选择排序，堆排序，基数排序这几种。
通过对各种排序方法的比较，我们能够很直观的发现各种排序方法的特点及各自的优缺点。
此次课程设计主要挑选了选择排序、插入排序、冒泡排序这三种排序方法，通过对这三种排序方法的比较，希望能够让大家对一些排序方法有更加直观、深入的了解。
设计中主要解决了用time()、srand()函数辅助rand()函数随机产生了0到99999之间的数据；借助指针申请了动态内存解决了将同一随机数组的三次复制进而确保在相同随机数组的基础上三种比较算法的比较；在各种算法中运用clock()函数计算完成比较所用的时间，并在各种比较算法的编程理解中完成比较、交换次数的计数；将随机数组写入文件等问题。
关键词：随机数
排序
交换
时间
目录
1.
设计内容、设计参数及要求·······································1
1.1
设计内容···················································1
1.2
设计参数···················································1
1.3
要求·······················································1
2.
总体设计思路···················································2
2.1
设计系统的功能·············································2
2.2
算法思想···················································2
2.3
系统的总体框架·············································3
2.4
系统的总体流程图···········································4
3.
功能模块的具体设计·············································5
3.1
main(
)主函数···············································5
3.2
SelectSort(
)函数·············································7
3.3
InsertSort(
)函数·············································9
3.4
PopSort(
)函数··············································11
3.5
将随机数写入程序··········································13
3.6
welcome(
)函数·············································14
4.
模块的调试及测试··············································15
5.
总结与个人体会················································17
5.1
总结······················································17
5.2
个人体会··················································17
6.
致谢··························································19
7.
参考文献······················································20
附程序源代码·····················································21
1.
设
计
内
容
和
要
求
1.1
设计内容
⑴通过随机函数随机生成100000个数字，这些数字都是在[0，99999]之间。
(2)并通过设计的排序算法进行排序。这些排序算法中包括冒泡法、选择法、插入法，也可以适当选择其他算法，但必须是较为典型的排序算法。
(3)排序完毕后应给出相应的比较信息，其中包括排序时间，比较次数和交换次数等信息。
(4)在程序的主界面显示出最后的比较结论。
(5)查看完比较结果后，即可点击回车退出系统
1.2
设计参数
(1)将排序前生成的100000个随机数存入一个文本文件中，该文件命名为BeforeSort.txt。
(2)将排序好的数字分别按照不同的排序方式存入不同的文件中，冒泡法排序后的数字存入PopSort.txt中，选择法排序后的数字存入SelectSort.txt中，插入法排序后的数字存入InsertSort.txt中。
1.3
要求
1.3.1
基本要求
精确测试上述三种排序方法对同样的数据进行排序所消耗的时间，比较次数以及交换次数，明确各种排序的编写方法，分析各种排序方法在不同情况下的优劣。
1.3.2
附加要求
（1）程序启动后有较漂亮的封面页。
(2
)
结果以列表形式，较友好的人机界面显示
2.
总
体
设
计
思
路
2.1
设计系统的功能
⑴在“Before.txt”中存储随机数。
⑵在”SelectSort.txt”、”InsertSort.txt”、”PopSort.txt”
中存储经过排序后的有序数列。
⑶通过对主界面中三种排序方法所用时间、比较次数、交换次数等信息的观察，了解到各自排序方法的特点及优劣。
2.2
算法思路
2.1.1
选择排序
为了便于理解，设有10个数分别存在数组元素a[0]～a[9]中。选择排序法是由大到小依次定位a[0]～a[9]中恰当的值，a[9]中放的自然是最小的数。如定位a[0],先假定a[0]中当前值是最大数，a[0]与后面的元素一一比较，如果a[4]更大，则将a[0]、a[4]交换，a[0]已更新再与后面的a[5]～a[9]比较，如果a[8]还要大，则将a[0]、a[8]交换，a[0]又是新数，再与a[9]比较。一轮比完以后，a[0]就是最大的数了，本次比武的武状元诞生了，接下来从a[1]开始，再来一轮a[1]就是次大的数，然后从a[2]开始，当比到a[8]以后，排序就完成了。
2.2.2
插入排序
每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序，直到待排序数据元素全部插入完为止。即经过i-1遍处后,L[1i-1]己排好序。第i遍处理仅将L插入L[1i-1]的适当位置p，原来p后的元素一一向右移动一个位置,使得L[1i]又是排好序的序列。
2.2.3冒泡排序
首先将第一个记录的随机数和第二个记录的随机数进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的随机数。依此类推，直到第N-1和第N个记录的随机数进行过比较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序，对前N-1个记录进行同样操作。一共要进行N-1趟起泡排序
2.3系统的总体框架图
登录
选择排序
插入排序
冒泡排序
将排序结果放入文件
将排序结果放入文件
将排序结果放入文件
结束
主函数
退出
2.4
系统的总体流程图
调用随机数函数，产生10000个随机数
打开一个“BeforeSort.txt”文本文档，将这10000个随机数放到文本文档中
选择排序，并得出其时间消耗，比较次数，交换次数
插入排序，并得出其时间消耗，比较次数，交换次数
冒泡排序，并得出其时间消耗，比较次数，交换次数
将经过选择排序好的10000个数字存放到“SelectSort.txt”文本文档
将经过插入排序好的10000个数字存放到“InsertSort.txt”文本文档
将经过排序好的10000个数字存放到“PopSort.txt”文本文档
程序结束
退出
进入登录界面
按“Enter”键进入主界面
3.功能模块的具体设计
3.1
main(
)
主函数
主函数功能比较简单，用srand(
(unsigned)time(
NULL
)
)语句以及for循环语句产生随机数。打开“BeforeSort.txt“文本文档，将随机数放入该文本文档中。使用动态内存，定义选择、插入、冒泡三种排序方法。在主函数的前面要写必须的头文件，预定义语句。
3.1.1随机函数的产生
函数rand()将产生一个在0到RAND_MAX之间的整数，其中RAND_MAX是头文件中定义的一个符号常量，并且至少是32767，即16位二进制数所能表示的最大整数。并可以利用比例缩放（求余运算）产生一系列0到所需数（小于RAND_MAX）之间的数
。但实际操作中最大只能得到0到10000之间的数，所以采用了分别获取0到10000之间的数加上0到10之间的数最终得到0到100000之间的数的方法。
但是rand()函数具有重复性，并且这种重复性可用于验证该函数运行正确与否，故要借助srand()、time()对该函数进行随机化。其中，函数time的返回值是以秒为单位的从1970年1月1日午夜开始到现在所经历的时间，time函数的返回值被转换成一个无符号的种子传递给srand()函数以产生随机数
表3.1.1
随机数的产生
中间变量
R[i]
=
k
a=
rand()%10000
b
=
a*10
c
=
rand()%10
k
=
b+c
R
[0]
5465
R[1]
723
R[2]
8421
R[3]
69
R[4]
3623
……
……
i
=
0
i
#include
void
main()
{
clock_t
start;
clock_t
end;
int
t;
long
i;
start=clock();
//得到程序运行时的时间量的值
for(i=0;i=0;j--)
{
cpt2++;
if(temp>=R[j])
break;
R[j+1]=R[j];
}
R[j+1]=temp;
if(j+1==i-1)
count2++;
else
count2=count2+0;
}
i
=
1
i
=
0
break
是
真
假
图3.3.1
插入排序流程图
3.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;iR[j+1])
{
count3++;
t=R[j];
R[j]=R[j+1];
R[j+1]=t;
}
cpt4++;
}
}
i
=
1
i
R[j+1]
t
=R[j]
int
i,j,t,double
count3,cpt4
R[j]=R[j+1]
R[j+1]=
t
cpt4++
j
++
count3++
i++
真
真
真
假
图3.4.1
冒泡排序流程图
3.5将随机数组写入文件
3.5.1
随机数组写入程序
intp=NULL;
FILE*fp;
if((fp=fopen(“BeforeSort.txt“,“w“))
==
NULL)
{
printf(“error“);
exit(0);
}for(i=0;i
#include
#include
#include
void
welcome();
void
time();
void
SelectSort(int
R[
],int
n);
void
InsertSort(int
R[
],int
n);
void
PopSort(int
R[
],int
n);
void
main(
)
//主函数
{
system(“color
2f“);
welcome();
int
i,k,a,b,c,R[100000],n;
intp=NULL;
FILE*fp;
srand(
(unsigned)time(
NULL
)
);
for(
i
=
0;
i
=0;j--)
{
cpt2++;
if(temp>=R[j])
break;
R[j+1]=R[j];
}
R[j+1]=temp;
if(j+1==i-1)
count2++;
else
count2=count2+0;
}
if((fp=fopen(“InsertSort.txt“,“w“))
==
NULL)
{
printf(“error“);
exit(0);
}
for(i=0;iR[j+1])
{
count3++;
t=R[j];
R[j]=R[j+1];
R[j+1]=t;
}
cpt4++;
}
}
if((fp
=fopen(“Popsort.txt“,“w“))==
NULL)
{
printf(“error“);
exit(0);
}
for(i=0;i { fprintf(fp,“%d “,R[i]); } if(fclose(fp)) { printf(“Can not close the file“); exit(0); } end=clock(); time3=(double)(end-start)/CLOCKS_PER_SEC; printf(“====================================/n“); printf(“PopSort:/n“); printf(“pop Sort Spend %.2lf seconds/n“,time3); printf(“pop Sort Compare %.0lf times/n“,cpt4); printf(“pop Sort Swap %.0lf times/n“,count3); printf(“/n/n“); } void welcome() { printf(“/n“); printf(“/n“); printf(“┏━━━━━━━━━━━━━━━━━━━━━━━┓/n“); printf(“┃ 各种排序算法比较 ┃/n“); printf(“┃---------------------------------------------------------------------┃ /n“); printf(“┃ (c)All Right Reserved wyy ┃/n“); printf(“┃ wcnumberond@163.com ┃/n“); printf(“┃ version 2009 ┃/n“); printf(“┗━━━━━━━━━━━━━━━━━━━━━━━┛/n“); printf(“Press Enter to Continue……“); getchar(); system(“cls“);