排序算法的比较及时间.doc

/*题目：排序算法比较 设计目的:1 掌握各种排序的基本思想。 2 掌握各种排序方法的算法实现。 3 掌握各种排序方法的优劣分析及花费的时间的计算。 4 掌握各种排序方法所适应的不同场合。二、 设计内容和要求 利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间。函数说明cha_ru_sort(int nData, unsigned int nNum) 插入排序maopao_sort(int maopao_data,int maopao_n) 起泡排序select_sort(int *Data,int nLen) 选择排序QuickSort(int* pData,int nLen) 快速排序HeapSort(int array,int length) 堆排序MergeSort(int sourceArr, int targetArr, int startIndex, int endIndex) 归并排序无参数返回*/#include#include/#includestdlib.h?/随机函数头文件#include#define rand_number 30000 /产生随机数的个数int rand_numbers_30000_0rand_number=0,rand_numbers_30000_1rand_number=0;int min,max; /随机数的范围/*/功能：产生随机数/无参数返回/*void produce_rand_num() int i;for(i=0;irand_number;i+)rand_numbers_30000_0i=min+rand()%max; /*/函数名：插入排序/功能描述：插入排序从下到大，nData为要排序的数据,nNum为数据的个数,该排序是稳定的排序/一个数就是已经排列好的了，所以从数组第二个数开始进行插入排序/无参数返回/*/void cha_ru_sort(int nData, unsigned int nNum)unsigned int i,j,k;for( i = 1 ; i nNum; i+) int nTemp = nDatai; /从数组中的第二个数开始获取数据for( j = 0 ; j nTemp)/找到位置，然后插入该位置，之后的数据后移for( k = i; k j ;-k)/数据后移nDatak=nDatak-1;nDataj=nTemp;/将数据插入到指定位置break;/*/函数名：冒泡排序/功能描述：/*/冒泡排序,maopao_data要排序的数据，maopao_n数据的个数void maopao_sort(int maopao_data,int maopao_n)unsigned char flag=0;/flag为1表示排序结束，初始化为0int i,j;int nTemp;/i从0,maopao_n-1)开始冒泡，确定第i个元素for( i=0 ; imaopao_n-1 ; i+)/比较maopao_n-1次/从maopao_n - 1, i）检查是否比上面一个小，把小的冒泡浮上去for(j=0;j maopao_dataj+1) /如果下面的比上面小，交换 nTemp=maopao_dataj;maopao_dataj = maopao_dataj+1;maopao_dataj+1=nTemp;/ /*/函数名：选择排序/功能描述：/*/选择排序/选择排序,pnData要排序的数据，nLen数据的个数void select_sort(int *Data,int nLen)int nIndex,i,j,nTemp;/i从0,nLen-1)开始选择，确定第i个元素for(i=0;inLen-1;i+) nIndex=i;/遍历剩余数据，选择出当前最小的数据for(j=i+1;jnLen;j+)if(DatajDatanIndex) nIndex=j;/如果当前最小数据索引不是i，也就是说排在i位置的数据不在nIndex处if(nIndex!=i)/交换数据，确定i位置的数据。 nTemp=Datai;Datai=DatanIndex;DatanIndex=nTemp;/*/函数描述：快速排序/*/化分区间,找到最后元素的排序位置。并返回分隔的点（即最后一数据排序的位置）。/划分的区间是nBegin,nEnd) .pData是保存数据的指针int position(int *pData, int nBeging, int nEnd)int j,i,nD,nTemp;nEnd-;i=nBeging-1;/分隔符号，最后nD保存在这里nD=pDatanEnd;/比较的数据。/遍历数据比较，找到nD的位置，这里注意，比较结果是,/如果i的左边是小于等于nD的，i的右边是大于nD的for(j=nBeging;jnEnd;+j)if(pDataj=nEnd-1)/如果区域不存在或只有一个数据则不递归排序return 1;/这里因为分割的时候，分割点处的数据就是排序中他的位置。/也就是说他的左边的数据都小于等于他，他右边的数据都大于他。/所以他不在递归调用的数据中。i=position(pData,nBeging,nEnd);/找到分割点QuickSortRecursion(pData,nBeging,i);/递归左边的排序QuickSortRecursion(pData,i+1,nEnd);/递归右边的排序return 1;/快速排序void QuickSort(int* pData,int nLen)/递归调用，快速排序。QuickSortRecursion(pData,0,nLen);/*/函数名：堆排序/功能描述：/*/void HeapAdjust(int array, int i, int nLength) int nChild; int nTemp; for (nTemp = arrayi; 2 * i + 1 nLength; i = nChild) / 子结点的位置=2*（父结点位置）+ 1 nChild = 2 * i + 1; / 得到子结点中较大的结点 if ( nChild arraynChild) +nChild; / 如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点 if (nTemp = 0; -i) HeapAdjust(array, i, length); / 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素 for (i = length - 1; i 0; -i) / 把第一个元素和当前的最后一个元素交换， / 保证当前的最后一个位置的元素都是在现在的这个序列之中最大的 / Swap(&array0, &arrayi); tmp = arrayi; arrayi = array0; array0 = tmp; / 不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值 HeapAdjust(array, 0, i); /*/函数名：归并排序/功能描述：将sourceArr中的数据排序，按顺序存入targetArr数组中，排序的个数从/ startIndex开始到endIndex/*/void Merge(int sourceArr, int targetArr, int startIndex, int midIndex, int endIndex)int i, j, k;for(i = midIndex+1, j = startIndex; startIndex = midIndex & i = endIndex; j+)if(sourceArrstartIndex sourceArri)targetArrj = sourceArrstartIndex+;elsetargetArrj = sourceArri+;if(startIndex = midIndex)for(k = 0; k = midIndex-startIndex; k+)targetArrj+k = sourceArrstartIndex+k;if(i = endIndex)for(k = 0; k = endIndex- i; k+)targetArrj+k = sourceArri+k;/内部使用递归，空间复杂度为n+lognvoid MergeSort(int sourceArr, int targetArr, int startIndex, int endIndex)int midIndex;int tempArr100; /此处大小依需求更改if(startIndex = endIndex)targetArrstartIndex = sourceArrstartIndex;elsemidIndex = (startIndex + endIndex)/2;MergeSort(sourceArr, tempArr, startIndex, midIndex);MergeSort(sourceArr, tempArr, midIndex+1, endIndex);Merge(tempArr, targetArr,startIndex, midIndex, endIndex);/*/void main() long int go_time; /所用时间 time_t t1,t2;/time_t是表示时间的结构体，t1为开始时间。t2为结束时 printf(n); printf(n); printf(n); printf(n); printf(n); printf(t产生随机数的个数为30000个); printf(n); printf(t请输入随机数范围，先最小值，后最大值,按回车结束:); scanf(%d%d,&min,&max); printf(n); printf(n); produce_rand_num(); t1=time(NULL);/得到的是秒 cha_ru_sort(rand_numbers_30000_0, rand_number); t2=time(NULL);/得到的是秒 go_time=t2-t1; printf(t插入排序用的时间为%d秒,go_time); printf(n); produce_rand_num(); t1=time(NULL);/得到的是秒 maopao_sort(rand_numbers_30000_0,rand_number); t2=time(NULL);/得到的是秒 go_time=t2-t1; printf(t起泡排序用的时间为%d秒,go_time); printf(n); produce_rand_num(); t1=time(NULL);/得到的是秒 select_sort(rand_numbers_30000_0,rand_number); t2=time(NULL);/得到的是秒 go_time=t2-t1; printf(t选择排序用的时间为%d秒,go_time); printf(n); produce_rand_num(); t1=time(NULL);/得到的是秒 QuickSort(rand_numbers_30000_0,rand_number); t2=time(NULL);/得到的是秒 go_time=t2-t1; printf(t快速排序用的时间为%d秒,go_time); printf(n); produce_rand_num(); t1=time(NULL);/得到的是秒 HeapSort(rand_numbers_30000_0,rand_number); t2=time(NULL);/得到的是秒 go_time=t2-t1; printf(t堆排序用的时间为%d秒,go_time); pri