题目：排序算法比较设计目的: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<stdio.h>#include<stdlib.h>//#include"stdlib.h"??//随机函数头文件#include<time.h>#define rand_number 30000 //产生随机数的个数int rand_numbers_30000_0[rand_number]={0},rand_numbers_30000_1[rand_number]={0}; int min,max; //随机数的范围//***************************************************************//功能：产生随机数//无参数返回void produce_rand_num(){int i;for(i=0;i<rand_number;i++){rand_numbers_30000_0[i]=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 = nData[i]; //从数组中的第二个数开始获取数据for( j = 0 ; j < i; j++)//对该数，寻找他要插入的位置{if(nData[j]>nTemp)//找到位置，然后插入该位置，之后的数据后移{for( k = i; k > j ;--k)//数据后移{nData[k]=nData[k-1];}nData[j]=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 ; i<maopao_n-1 ; i++)//比较maopao_n-1次{//从[maopao_n - 1, i）检查是否比上面一个小，把小的冒泡浮上去for(j=0;j<maopao_n- 1 -i ; j++){if( maopao_data[j] > maopao_data[j+1]) //如果下面的比上面小，交换{nTemp=maopao_data[j];maopao_data[j] = maopao_data[j+1];maopao_data[j+1]=nTemp;}}}}///****************************************************************************** ***///函数名：选择排序////功能描述：/****************************************************************************** ***///选择排序//选择排序,pnData要排序的数据，nLen数据的个数void select_sort(int *Data,int nLen){int nIndex,i,j,nTemp;//i从[0,nLen-1)开始选择，确定第i个元素for(i=0;i<nLen-1;i++){nIndex=i;//遍历剩余数据，选择出当前最小的数据for(j=i+1;j<nLen;j++){if(Data[j]<Data[nIndex]){nIndex=j;}}//如果当前最小数据索引不是i，也就是说排在i位置的数据不在nIndex处if(nIndex!=i){//交换数据，确定i位置的数据。
nTemp=Data[i];Data[i]=Data[nIndex];Data[nIndex]=nTemp;}}}/****************************************************************************** ***///函数描述：快速排序///////****************************************************************************** ***///化分区间,找到最后元素的排序位置。
并返回分隔的点（即最后一数据排序的位置）。
//划分的区间是[nBegin,nEnd) .pData是保存数据的指针int position(int *pData, int nBeging, int nEnd){int j,i,nD,nTemp;nEnd--;i=nBeging-1;//分隔符号，最后nD保存在这里nD=pData[nEnd];//比较的数据。
//遍历数据比较，找到nD的位置，这里注意，比较结果是,//如果i的左边是小于等于nD的，i的右边是大于nD的for(j=nBeging;j<nEnd;++j){if(pData[j]<=nD)//如果数据比要比较的小，则在该数据的左边，与i+1交换{i++;//小于nD的数据多一个，所以要加1，i的左边数据都比nD小nTemp=pData[i];//交换数据pData[i]=pData[j];pData[j]=nTemp;}}//最后不要忘了吧nD和i+1交换，因为这里就是nD的位置咯。
++i;pData[nEnd]=pData[i];pData[i]=nD;return i;//返回nD的位置，就是分割的位置。
}//排序的递归调用。
int QuickSortRecursion(int *pData,int nBeging,int nEnd){int i;if(nBeging>=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 = array[i]; 2 * i + 1 < nLength; i = nChild){// 子结点的位置=2*（父结点位置）+ 1nChild = 2 * i + 1;// 得到子结点中较大的结点if ( nChild < nLength-1 && array[nChild + 1] > array[nChild])++nChild;// 如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点if (nTemp < array[nChild]){array[i] = array[nChild];array[nChild]= nTemp;}else// 否则退出循环break;}}// 堆排序算法void HeapSort(int array[],int length){int tmp,i;// 调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素//length/2-1是第一个非叶节点，此处"/"为整除for (i = floor(length -1)/ 2 ; i >= 0; --i)HeapAdjust(array, i, length);// 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素for (i = length - 1; i > 0; --i){// 把第一个元素和当前的最后一个元素交换，// 保证当前的最后一个位置的元素都是在现在的这个序列之中最大的/// Swap(&array[0], &array[i]);tmp = array[i];array[i] = array[0];array[0] = 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(sourceArr[startIndex] < sourceArr[i]){targetArr[j] = sourceArr[startIndex++];}else{targetArr[j] = sourceArr[i++];}}if(startIndex <= midIndex){for(k = 0; k <= midIndex-startIndex; k++){targetArr[j+k] = sourceArr[startIndex+k];}}if(i <= endIndex){for(k = 0; k <= endIndex- i; k++){targetArr[j+k] = sourceArr[i+k];}}//内部使用递归，空间复杂度为n+lognvoid MergeSort(int sourceArr[], int targetArr[], int startIndex, int endIndex){int midIndex;int tempArr[100]; //此处大小依需求更改if(startIndex == endIndex){targetArr[startIndex] = sourceArr[startIndex];}else{midIndex = (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为开始时间。
