1、double TInsertSort（int a,int p），还有显示菜单的模块void menu（）和显示排序结果模块void Disp（int a）等等，各个模块之间可以互相调用，节省了资源。用case作为各个功能的入口。用QueryPerformanceFrequency（）和QueryPerformanceCounte（）函数计时，精度比用clock（）高，避免了很多时候因排序速度太快而出现运行时间为0的现象。用srand函数作为随机数发生器的初始化函数，用rand产生随机数。把计算得的排序时间存入数组并经冒泡排序得出最快的两种排序法。下面是所用排序法的算法思想：（1）直接插入排序的
2、基本思想是基于插入，开始假定第一个记录有序，然后从第二个记录开始，依次插入到前面有序的子文件中。即将记录ai（2=i=n）插入到有序子序列a1.i-1中，使记录的有序序列从a1.i-1变为a1.i ，最终使整个文件有序。共进行n-1趟插入。最坏时间复杂度是0（n2），平均时间复杂度是0（n2），空间复杂度是O（1），是稳定排序。（2）直接选择排序的基本思想是基于选择，开始有序序列长度为零，第i（1n）趟简单选择排序是，从无序序列ai.n的n-i+1记录中选出关键字最小的记录，和第i个记录交换，使有序序列逐步扩大，最后整个文件有序。共进行n-1趟选择。最坏时间复杂度是0（n2），平均时间复杂度是
3、0（n2），空间复杂度是O（1），是不稳定排序。（3）冒泡排序：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直到第N-1和第N个记录的关键字进行过比较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序，对前N-1个记录进行同样操作。一共要进行N-1趟起泡排序。（4）快速排序思想：从待排序列中任取一个元素 （例如取第一个） 作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子
4、表的元素只剩一个。此时便为有序序列了。（6）堆排序基本思想是：堆是n个元素的序列，先建堆，即先选得一个关键字最大或最小的记录，然后与序列中最后一个记录交换，之后将序列中前n-1记录重新调整为堆（调堆的过程称为“筛选”），再将堆顶记录和当前堆序列的最后一个记录交换，如此反复直至排序结束。优点是在时间性能与树形选择排序属同一量级的同时，堆排序只需要一个记录大小供交换用的辅助空间，调堆时子女只和双亲比较。避免了过多的辅助存储空间及和最大值的比较。2.3 主要算法和处理流程图3 程序实现3.1 程序实现时应考虑的问题模块化能使节约资源，也方便了程序的调试和增加功能。3.2 主要源代码及说明#inclu
5、de conio.h stdlib.hwindows.htime.h#define N 30000void Wrong（） printf（n=按键错误!n）;getchar（）;void Disp（int a）int i;system（cls for（i=0;i0&aj-1temp;j-） aj=aj-1; aj=temp; void SelectSort（int a,int p） /选择排序 int i,j,k;N-1; k=i; for（j=i+1;jj+） if（ajak） k=j; if（k!=i） int temp; temp=ak; ak=ai; ai=temp; void Bub
6、bleSort（int a,int p） /*冒泡排序算法*/int i,j,temp;for （i=0; for （j=N-1;i;j-） /*比较,找出本趟最小关键字的记录*/ if （ajaj-1） temp=aj; /*进行交换,将最小关键字记录前移*/ aj-1=temp;void creatheap（int a,int i,int n） /创建堆 int j;int t; t=ai; j=2*（i+1）-1; while（j=n） if（jn）&（ajaj+1） j+; if（t=0;i-） creatheap（a,i,n-1）; for（i=n-1;=1; t=a0; a0=ai
7、; ai=t; creatheap（a,0,i-1）;void quicksort（int a,int n,int p） int i,j,low,high,temp,top=-1; struct node int low,high; stN; top+; sttop.low=0;sttop.high=n-1; while（top-1） low=sttop.low;high=sttop.high; top-; i=low;j=high; if（lowhigh） temp=alow; while（i!=j） while（itemp）j-; if（ij）ai=aj;i+; while（iaitemp
8、）i+;j）aj=ai;j-;sttop.low=low;sttop.high=i-1;sttop.low=i+1;sttop.high=high;double TInsertSort（int a,int p）int bN; bi=ai;LARGE_INTEGER m_liPerfFreq=0;QueryPerformanceFrequency（&m_liPerfFreq）; LARGE_INTEGER m_liPerfStart=0; QueryPerformanceCounter（&m_liPerfStart）;InsertSort（b,p）;LARGE_INTEGER liPerfNow
9、=0;liPerfNow）; double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;if（p!=6）Disp（b）;n用直接插入排序法用的时间为%f秒；,time）;FILE *fp; fp=fopen（直接插入排序.txt,w fprintf（fp,%d ,bi）; fclose（fp）;return（time）;double TSelectSort（int a,int p）for（i=0;bi=ai; SelectSort（b,p）;n用直接选择排序法用的时间为%f秒； FI
10、LE *fp;直接选择排序.txtfclose（fp）;double TBubbleSort（int a,int p）BubbleSort（b,p）;n用冒泡排序法用的时间为%f秒；冒泡排序.txtdouble Theapsort（int a,int n,int p） heapsort（b,N,p）; Disp（b）;n用堆排序法用的时间为%f秒；堆排序.txtdouble Tquicksort（int a,int n,int p）quicksort（b,N,p）;n用快速排序法用的时间为%f秒；fp=fopen（快速排序.txt return（time）;void BubleSort（dou
11、ble a） /时间数组的冒泡排序 int i,j; double temp;6; for（j=4;=i; if（aj+1请在上述序号中选择一个并输入:void main（） int i,p,aN; srand（int）time（NULL）; /*随机种子*/ ai=rand（）%50000+1; while（1） system（ menu（）; scanf（%d,&p）; if（p=0）=谢谢使用! getchar（）; break;double TIMES5,TIMES15;/时间数组 switch（p） case 1:TInsertSort（a,p）;n请按任意键继续.break; ca
12、se 2:TSelectSort（a,p）; case 3:TBubbleSort（a,p）; case 4:Tquicksort（a,N,p）; case 5:Theapsort（a,N,p）; case 6:TIMES11=TIMES1=TInsertSort（a,p）;TIMES12=TIMES2=TSelectSort（a,p）; TIMES13=TIMES3=TBubbleSort（a,p）;TIMES14=TIMES4=Tquicksort（a,N,p）;TIMES15=TIMES5=Theapsort（a,N,p）; BubleSort（TIMES）;nn printf（排序这组
13、数据两种较快的排序法分别是： if（TIMES1=TIMES11） printf（直接插入排序:%f秒!,TIMES1）; if（TIMES1=TIMES12） printf（直接选择排序: if（TIMES1=TIMES13） printf（冒泡排序: if（TIMES1=TIMES14） printf（快速排序: if（TIMES1=TIMES15） printf（堆排序: if（TIMES1!=TIMES2） if（TIMES2=TIMES11） printf（,TIMES2）; if（TIMES2=TIMES12） printf（直接选择排序%f秒! if（TIMES2=TIMES13） printf（冒泡排序%f秒! if（TIMES2=TIMES14） printf（快速排序%f秒! if（TIMES2=TIMES15） printf（堆排序%f秒! printf（srand（int）time（NULL）;i+） ai=rand（）%30000+1; getchar（）;case 7:Disp（a）;随机数.txti+）fprintf（fp,default:Wrong（）;n请按任意键继续.
