ZT 9种排序

9种排序

 66人阅读 评论(0) 收藏 编辑 删除
  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <windows.h>  
  4. #include <time.h>  
  5. void Swap(float &x, float &y)  
  6. {  
  7.     x = x + y;  
  8.     y = x - y;  
  9.     x = x - y;  
  10. }  
  11.   
  12. void PrintData(int *pDataArray, int iDataNum)  
  13. {  
  14.     for (int i = 0; i < iDataNum; i++)  
  15.         printf("%d ", pDataArray[i]);  
  16.     printf("\n");  
  17.     fflush(stdout);  
  18. }  
  19.   
  20. //交换data1和data2所指向的整形  
  21. void DataSwap(int* data1, int* data2)  
  22. {  
  23.     int temp = *data1;  
  24.     *data1 = *data2;  
  25.     *data2 = temp;  
  26. }  
  27.   
  28.   
  29. /******************************************************** 
  30. *函数名称:ShellInsert 
  31. *参数说明:pDataArray 无序数组; 
  32. *          d          增量大小 
  33. *          iDataNum为无序数据个数 
  34. *说明:    希尔按增量d的插入排序 
  35. *********************************************************/  
  36. void ShellInsert(int* pDataArray, int d, int iDataNum)  
  37. {  
  38.     for (int i = d; i < iDataNum; i += 1)    //从第2个数据开始插入  
  39.     {  
  40.         int j = i - d;  
  41.         int temp = pDataArray[i];    //记录要插入的数据  
  42.         while (j >= 0 && pDataArray[j] > temp)    //从后向前,找到比其小的数的位置  
  43.         {  
  44.             pDataArray[j+d] = pDataArray[j];    //向后挪动  
  45.             j -= d;  
  46.         }  
  47.   
  48.         if (j != i - d)    //存在比其小的数  
  49.             pDataArray[j+d] = temp;  
  50.     }  
  51. }  
  52.   
  53. /******************************************************** 
  54. *函数名称:ShellSort 
  55. *参数说明:pDataArray 无序数组; 
  56. *          iDataNum为无序数据个数 
  57. *说明:    希尔排序 
  58. *********************************************************/  
  59. void ShellSort(int* pDataArray, int iDataNum)  
  60. {  
  61.     int d = iDataNum / 2;    //初始增量设为数组长度的一半  
  62.     while(d >= 1)  
  63.     {  
  64.         ShellInsert(pDataArray, d, iDataNum);  
  65.         d = d / 2;    //每次增量变为上次的二分之一  
  66.     }  
  67. }  
  68.   
  69. /******************************************************** 
  70. *函数名称:GetNumInPos 
  71. *参数说明:num 一个整形数据 
  72. *          pos 表示要获得的整形的第pos位数据 
  73. *说明:    找到num的从低到高的第pos位的数据 
  74. *********************************************************/  
  75. int GetNumInPos(int num,int pos)  
  76. {  
  77.     int temp = 1;  
  78.     for (int i = 0; i < pos - 1; i++)  
  79.         temp *= 10;  
  80.   
  81.     return (num / temp) % 10;  
  82. }  
  83.   
  84. /******************************************************** 
  85. *函数名称:RadixSort 
  86. *参数说明:pDataArray 无序数组; 
  87. *          iDataNum为无序数据个数 
  88. *说明:    基数排序 
  89. *********************************************************/  
  90. #define RADIX_10 10    //整形排序  
  91. #define KEYNUM_31 10     //关键字个数,这里为整形位数  
  92. void RadixSort(int* pDataArray, int iDataNum)  
  93. {  
  94.     int *radixArrays[RADIX_10];    //分别为0~9的序列空间  
  95.     for (int i = 0; i < 10; i++)  
  96.     {  
  97.         radixArrays[i] = (int *)malloc(sizeof(int) * (iDataNum + 1));  
  98.         radixArrays[i][0] = 0;    //index为0处记录这组数据的个数  
  99.     }  
  100.   
  101.     for (int pos = 1; pos <= KEYNUM_31; pos++)    //从个位开始到31位  
  102.     {  
  103.         for (int i = 0; i < iDataNum; i++)    //分配过程  
  104.         {  
  105.             int num = GetNumInPos(pDataArray[i], pos);  
  106.             int index = ++radixArrays[num][0];  
  107.             radixArrays[num][index] = pDataArray[i];  
  108.         }  
  109.   
  110.         for (int i = 0, j =0; i < RADIX_10; i++)    //收集  
  111.         {  
  112.             for (int k = 1; k <= radixArrays[i][0]; k++)  
  113.                 pDataArray[j++] = radixArrays[i][k];  
  114.             radixArrays[i][0] = 0;    //复位  
  115.         }  
  116.     }  
  117. }  
  118.   
  119. /******************************************************** 
  120. *函数名称:SlipDown 
  121. *参数说明:pDataArray 无序数组; 
  122. *          iCurNode为堆中需要调整的节点 
  123. *          iDataNum为数组长度 
  124. *函数返回:分割后的分割数位置 
  125. *函数说明:调整iCurNode处的节点,形成大顶堆     
  126. *********************************************************/  
  127. void SlipDown(int *pDataArray,int iCurNode,int iDataNum)  
  128. {  
  129.     int temp = pDataArray[iCurNode];    //记录需要调整的节点值  
  130.   
  131.     for (int iNextNode = iCurNode*2; iNextNode <= iDataNum; iNextNode = iCurNode*2)  
  132.     {  
  133.         if (iNextNode + 1 <= iDataNum   
  134.             && pDataArray[iNextNode] < pDataArray[iNextNode + 1])    //寻找iCurNode子节点中的大者  
  135.             iNextNode++;  
  136.         if (pDataArray[iNextNode] > temp)    //大的值上移  
  137.             pDataArray[iCurNode] = pDataArray[iNextNode];      
  138.         else    //结束调整  
  139.             break;  
  140.   
  141.         iCurNode = iNextNode;    //更新需要调整的节点  
  142.     }  
  143.   
  144.     pDataArray[iCurNode] = temp;  
  145. }  
  146.   
  147. /******************************************************** 
  148. *函数名称:HeapSort 
  149. *参数说明:pDataArray 无序数组; 
  150. *          iDataNum为无序数据个数 
  151. *说明:    堆排序 
  152. *********************************************************/  
  153. void HeapSort(int* pDataArray, int iDataNum)  
  154. {  
  155.     pDataArray--;    //让原先数组下标0对应1,便于堆中节点的访问  
  156.     for (int i = iDataNum/2; i > 0; i--)    //调整为大顶堆  
  157.         SlipDown(pDataArray, i, iDataNum);  
  158.   
  159.     for (int i = iDataNum; i > 1; i--)    //根据大顶堆进行排序  
  160.     {  
  161.         DataSwap(&pDataArray[i], &pDataArray[1]);  
  162.         SlipDown(pDataArray, 1, i - 1);  
  163.     }  
  164. }  
  165.   
  166. /******************************************************** 
  167. *函数名称:Split 
  168. *参数说明:pDataArray 无序数组; 
  169. *          iBegin为pDataArray需要快速排序的起始位置 
  170. *          iEnd为pDataArray需要快速排序的结束位置 
  171. *函数返回:分割后的分割数位置 
  172. *说明:    以iBegin处的数值value作为分割数, 
  173. 使其前半段小于value,后半段大于value 
  174. *********************************************************/  
  175. int Split(int *pDataArray,int iBegin,int iEnd)  
  176. {  
  177.     int rIndex = rand() % (iEnd - iBegin + 1);    //随机获得偏移位置  
  178.   
  179.     int pData = pDataArray[iBegin + rIndex];    //将iBegin+rIndex处的值作为划分值  
  180.   
  181.     while (iBegin < iEnd)    //循环分割数组,使其前半段小于pData,后半段大于pData  
  182.     {  
  183.         while (iEnd > iBegin && pDataArray[iEnd] >= pData)    //从后向前寻找小于pData的数据位置  
  184.             iEnd--;  
  185.   
  186.         if (iEnd != iBegin)  
  187.         {  
  188.             pDataArray[iBegin] = pDataArray[iEnd];    //将小于pData数据存放到数组前方  
  189.             iBegin++;  
  190.   
  191.             while (iBegin < iEnd && pDataArray[iBegin] <= pData)  
  192.                 iBegin++;  
  193.   
  194.             if (iBegin != iEnd)  
  195.             {  
  196.                 pDataArray[iEnd] = pDataArray[iBegin];    //将大于pData数据存放到数组后方  
  197.                 iEnd--;  
  198.             }  
  199.         }  
  200.     }  
  201.   
  202.     pDataArray[iEnd] = pData;    //此时iBegin=iEnd,此处存储分割数据pData  
  203.     return iEnd;  
  204. }  
  205.   
  206. /******************************************************** 
  207. *函数名称:QSort 
  208. *参数说明:pDataArray 无序数组; 
  209. *          iBegin为pDataArray需要快速排序的起始位置 
  210. *          iEnd为pDataArray需要快速排序的结束位置 
  211. *说明:    快速排序递归函数 
  212. *********************************************************/  
  213. void QSort(int* pDataArray, int iBegin, int iEnd)  
  214. {  
  215.     if (iBegin < iEnd)  
  216.     {  
  217.         int pos = Split(pDataArray, iBegin, iEnd);    //获得分割后的位置  
  218.         QSort(pDataArray, iBegin, pos - 1);           //对分割后的前半段递归快排  
  219.         QSort(pDataArray, pos + 1, iEnd);             //对分割后的后半段递归快排  
  220.     }  
  221. }  
  222.   
  223. /******************************************************** 
  224. *函数名称:QuickSort 
  225. *参数说明:pDataArray 无序数组; 
  226. *          iDataNum为无序数据个数 
  227. *说明:    快速排序 
  228. *********************************************************/  
  229. void QuickSort(int* pDataArray, int iDataNum)  
  230. {  
  231.     QSort(pDataArray, 0, iDataNum - 1);  
  232. }  
  233.   
  234.   
  235. /******************************************************** 
  236. *函数名称:Merge 
  237. *参数说明:pDataArray 无序数组; 
  238. *          int *pTempArray 临时存储合并后的序列 
  239. *          bIndex 需要合并的序列1的起始位置 
  240. *          mIndex 需要合并的序列1的结束位置 
  241. 并且作为序列2的起始位置 
  242. *          eIndex 需要合并的序列2的结束位置 
  243. *说明:    将数组中连续的两个子序列合并为一个有序序列 
  244. *********************************************************/  
  245. void Merge(int* pDataArray, int *pTempArray, int bIndex, int mIndex, int eIndex)  
  246. {  
  247.     int mLength = eIndex - bIndex;    //合并后的序列长度  
  248.     int i = 0;    //记录合并后序列插入数据的偏移  
  249.     int j = bIndex;    //记录子序列1插入数据的偏移  
  250.     int k = mIndex;    //记录子序列2掺入数据的偏移  
  251.   
  252.     while (j < mIndex && k < eIndex)  
  253.     {  
  254.         if (pDataArray[j] <= pDataArray[k])  
  255.         {  
  256.             pTempArray[i++] = pDataArray[j];  
  257.             j++;  
  258.         }  
  259.         else  
  260.         {  
  261.             pTempArray[i++] = pDataArray[k];  
  262.             k++;  
  263.         }  
  264.     }  
  265.   
  266.     if (j == mIndex)    //说明序列1已经插入完毕  
  267.         while (k < eIndex)  
  268.             pTempArray[i++] = pDataArray[k++];  
  269.     else                //说明序列2已经插入完毕  
  270.         while (j < mIndex)  
  271.             pTempArray[i++] = pDataArray[j++];  
  272.   
  273.     for (i = 0; i < mLength; i++)    //将合并后序列重新放入pDataArray  
  274.         pDataArray[bIndex + i] = pTempArray[i];  
  275. }  
  276.   
  277. /******************************************************** 
  278. *函数名称:BottomUpMergeSort 
  279. *参数说明:pDataArray 无序数组; 
  280. *          iDataNum为无序数据个数 
  281. *说明:    自底向上的归并排序 
  282. *********************************************************/  
  283. void BottomUpMergeSort(int* pDataArray, int iDataNum)  
  284. {  
  285.     int *pTempArray = (int *)malloc(sizeof(int) * iDataNum);    //临时存放合并后的序列  
  286.     int length = 1;    //初始有序子序列长度为1  
  287.     while (length < iDataNum)  
  288.     {  
  289.         int i = 0;  
  290.         for (; i + 2*length < iDataNum; i += 2*length)  
  291.             Merge(pDataArray, pTempArray, i, i + length, i + 2*length);  
  292.         if (i + length < iDataNum)  
  293.             Merge(pDataArray, pTempArray, i, i + length, iDataNum);  
  294.         length *= 2;    //有序子序列长度*2  
  295.     }  
  296.     free(pTempArray);  
  297. }  
  298.   
  299. /******************************************************** 
  300. *函数名称:RecursionMergeSort 
  301. *参数说明:pDataArray 无序数组; 
  302. *          int *pTempArray 临时存放合并的序列 
  303. *          iBegin为pDataArray需要归并排序的起始位置 
  304. *          iEnd为pDataArray需要归并排序的结束位置 
  305. *说明:    自顶向下的归并排序递归函数 
  306. *********************************************************/  
  307. void RecursionMergeSort(int* pDataArray, int *pTempArray, int iBegin, int iEnd)  
  308. {  
  309.     if (iBegin < iEnd)  
  310.     {  
  311.         int middle = (iBegin + iEnd) / 2;  
  312.         RecursionMergeSort(pDataArray, pTempArray, iBegin, middle);    //前半段递归归并排序  
  313.         RecursionMergeSort(pDataArray, pTempArray, middle + 1, iEnd);  //后半段归并排序  
  314.         Merge(pDataArray, pTempArray, iBegin, middle + 1, iEnd + 1);   //合并前半段和后半段  
  315.     }  
  316. }  
  317.   
  318. /******************************************************** 
  319. *函数名称:UpBottomMergeSort 
  320. *参数说明:pDataArray 无序数组; 
  321. *          iDataNum为无序数据个数 
  322. *说明:    自顶向下的归并排序 
  323. *********************************************************/  
  324. void UpBottomMergeSort(int* pDataArray, int iDataNum)  
  325. {  
  326.     int *pTempArray = (int *)malloc(sizeof(int) * iDataNum);    //临时存放合并后的序列  
  327.     RecursionMergeSort(pDataArray, pTempArray, 0, iDataNum - 1);  
  328.     free(pTempArray);  
  329. }  
  330.   
  331. //查找数值iData在长度为iLen的pDataArray数组中的插入位置  
  332. int FindInsertIndex(int *pDataArray, int iLen, int iData)  
  333. {  
  334.     int iBegin = 0;  
  335.     int iEnd = iLen - 1;  
  336.     int index = -1;    //记录插入位置  
  337.     while (iBegin <= iEnd)  
  338.     {  
  339.         index = (iBegin + iEnd) / 2;  
  340.         if (pDataArray[index] > iData)  
  341.             iEnd = index - 1;  
  342.         else  
  343.             iBegin = index + 1;   
  344.     }  
  345.     if (pDataArray[index] <= iData)  
  346.         index++;  
  347.     return index;  
  348. }  
  349.   
  350. /******************************************************** 
  351. *函数名称:BinaryInsertSort 
  352. *参数说明:pDataArray 无序数组; 
  353. *          iDataNum为无序数据个数 
  354. *说明:    二分查找插入排序 
  355. *********************************************************/  
  356. void BinaryInsertSort(int* pDataArray, int iDataNum)  
  357. {  
  358.     for (int i = 1; i < iDataNum; i++)    //从第2个数据开始插入  
  359.     {  
  360.         int index = FindInsertIndex(pDataArray, i, pDataArray[i]);    //二分寻找插入的位置  
  361.   
  362.         if (i != index)    //插入位置不为i,才挪动、插入  
  363.         {  
  364.             int j = i;  
  365.             int temp = pDataArray[i];  
  366.             while (j > index)    //挪动位置  
  367.             {  
  368.                 pDataArray[j] = pDataArray[j-1];  
  369.                 j--;  
  370.             }  
  371.             pDataArray[j] = temp;    //插入  
  372.         }  
  373.     }  
  374. }  
  375.   
  376. /******************************************************** 
  377. *函数名称:InsertSort 
  378. *参数说明:pDataArray 无序数组; 
  379. *          iDataNum为无序数据个数 
  380. *说明:    插入排序(从前向后寻找) 
  381. *********************************************************/  
  382. void InsertSort(int* pDataArray, int iDataNum)  
  383. {  
  384.     for (int i = 1; i < iDataNum; i++)    //从第2个数据开始插入  
  385.     {  
  386.         int j = 0;  
  387.         while (j < i && pDataArray[j] <= pDataArray[i])    //寻找插入的位置  
  388.             j++;  
  389.   
  390.         if (j < i)    //i位置之前,有比pDataArray[i]大的数,则进行挪动和插入  
  391.         {  
  392.             int k = i;  
  393.             int temp = pDataArray[i];  
  394.             while (k > j)    //挪动位置  
  395.             {  
  396.                 pDataArray[k] = pDataArray[k-1];  
  397.                 k--;  
  398.             }  
  399.             pDataArray[k] = temp;    //插入  
  400.         }  
  401.     }  
  402. }  
  403.   
  404. /******************************************************** 
  405. *函数名称:InsertSort 
  406. *参数说明:pDataArray 无序数组; 
  407. *          iDataNum为无序数据个数 
  408. *说明:    插入排序(从后向前寻找) 
  409. *********************************************************/  
  410. void InsertSort1(int* pDataArray, int iDataNum)  
  411. {  
  412.     for (int i = 1; i < iDataNum; i++)    //从第2个数据开始插入  
  413.     {  
  414.         int j = i - 1;  
  415.         int temp = pDataArray[i];    //记录要插入的数据  
  416.         while (j >= 0 && pDataArray[j] > temp)    //从后向前,找到比其小的数的位置  
  417.         {  
  418.             pDataArray[j+1] = pDataArray[j];    //向后挪动  
  419.             j--;  
  420.         }  
  421.   
  422.         if (j != i - 1)    //存在比其小的数  
  423.             pDataArray[j+1] = temp;  
  424.     }  
  425. }  
  426.   
  427. /******************************************************** 
  428. *函数名称:SelectionSort 
  429. *参数说明:pDataArray 无序数组; 
  430. *          iDataNum为无序数据个数 
  431. *说明:    选择排序 
  432. *********************************************************/  
  433. void SelectionSort(int* pDataArray, int iDataNum)  
  434. {  
  435.     for (int i = 0; i < iDataNum - 1; i++)    //从第一个位置开始  
  436.     {  
  437.         int index = i;  
  438.         for (int j = i + 1; j < iDataNum; j++)    //寻找最小的数据索引   
  439.             if (pDataArray[j] < pDataArray[index])  
  440.                 index = j;  
  441.   
  442.         if (index != i)    //如果最小数位置变化则交换  
  443.             DataSwap(&pDataArray[index], &pDataArray[i]);  
  444.     }  
  445. }  
  446.   
  447. /******************************************************** 
  448. *函数名称:BubbleSort 
  449. *参数说明:pDataArray 无序数组; 
  450. *          iDataNum为无序数据个数 
  451. *说明:    冒泡排序 
  452. *********************************************************/  
  453. void BubbleSort(int* pDataArray, int iDataNum)  
  454. {  
  455.     BOOL flag = FALSE;    //记录是否存在交换  
  456.     for (int i = 0; i < iDataNum - 1; i++)    //走iDataNum-1趟  
  457.     {  
  458.         flag = FALSE;  
  459.         for (int j = 0; j < iDataNum - i - 1; j++)      
  460.             if (pDataArray[j] > pDataArray[j + 1])  
  461.             {  
  462.                 flag = TRUE;  
  463.                 DataSwap(&pDataArray[j], &pDataArray[j + 1]);  
  464.             }  
  465.   
  466.             if (!flag)    //上一趟比较中不存在交换,则退出排序  
  467.                 break;  
  468.     }  
  469. }  
  470.   
  471. //测试序列是否有序  
  472. BOOL CheckOrder(int *pDataArray, int iDataNum)  
  473. {  
  474.     for (int i = 0; i < iDataNum -  1; i++)  
  475.         if (pDataArray[i] > pDataArray[i+1])  
  476.             return FALSE;  
  477.     return TRUE;  
  478. }  
  479.   
  480. UINT64 time_fre;    //时钟频率  
  481.   
  482. UINT64 GetTimeM()  
  483. {  
  484.     //获取当前时间  
  485.     LARGE_INTEGER curCounter;  
  486.     QueryPerformanceCounter(&curCounter);  
  487.     return curCounter.QuadPart*1000/time_fre;  
  488. }  
  489.   
  490. void BubbleSortTest(int *pDataArray,int length, FILE *fp)  
  491. {  
  492.     //初始化数组  
  493.     for (int i = 0; i < length; i++)  
  494.         pDataArray[i] = rand()%100000;  
  495.   
  496.     UINT64 begin;  
  497.     UINT64 end;  
  498.     begin = GetTimeM();  
  499.     BubbleSort(pDataArray, length);  
  500.     end = GetTimeM();  
  501.   
  502.     fprintf(fp, " %d"int(end-begin));  
  503.   
  504.     if (!CheckOrder(pDataArray, length))  
  505.         printf("BubbleSort algorithm failed!\n");  
  506.     else  
  507.         printf("BubbleSort algorithm succeed!\n");  
  508. }  
  509.   
  510. void SelectSortTest(int *pDataArray,int length, FILE *fp)  
  511. {  
  512.     //初始化数组  
  513.     for (int i = 0; i < length; i++)  
  514.         pDataArray[i] = rand()%100000;  
  515.   
  516.     UINT64 begin;  
  517.     UINT64 end;  
  518.     begin = GetTimeM();  
  519.     SelectionSort(pDataArray, length);  
  520.     end = GetTimeM();  
  521.   
  522.     fprintf(fp, " %d"int(end-begin));  
  523.   
  524.     if (!CheckOrder(pDataArray, length))  
  525.         printf("SelectSort algorithm failed!\n");  
  526.     else  
  527.         printf("SelectSort algorithm succeed!\n");  
  528. }  
  529.   
  530. void InsertSortTest(int *pDataArray,int length, FILE *fp)  
  531. {  
  532.     //初始化数组  
  533.     for (int i = 0; i < length; i++)  
  534.         pDataArray[i] = rand()%100000;  
  535.   
  536.     UINT64 begin;  
  537.     UINT64 end;  
  538.     begin = GetTimeM();  
  539.     InsertSort(pDataArray, length);  
  540.     end = GetTimeM();  
  541.   
  542.     fprintf(fp, " %d"int(end-begin));  
  543.   
  544.     if (!CheckOrder(pDataArray, length))  
  545.         printf("InsertSort algorithm failed!\n");  
  546.     else  
  547.         printf("InsertSort algorithm succeed!\n");  
  548. }  
  549.   
  550. void BottomUpMergeSortTest(int *pDataArray,int length, FILE *fp)  
  551. {  
  552.     //初始化数组  
  553.     for (int i = 0; i < length; i++)  
  554.         pDataArray[i] = rand()%100000;  
  555.   
  556.     UINT64 begin;  
  557.     UINT64 end;  
  558.     begin = GetTimeM();  
  559.     BottomUpMergeSort(pDataArray, length);  
  560.     end = GetTimeM();  
  561.   
  562.     fprintf(fp, " %d"int(end-begin));  
  563.   
  564.     if (!CheckOrder(pDataArray, length))  
  565.         printf("BottomUpMergeSort algorithm failed!\n");  
  566.     else  
  567.         printf("BottomUpMergeSort algorithm succeed!\n");  
  568. }  
  569.   
  570. void UpBottomMergeSortTest(int *pDataArray,int length, FILE *fp)  
  571. {  
  572.     //初始化数组  
  573.     for (int i = 0; i < length; i++)  
  574.         pDataArray[i] = rand()%100000;  
  575.   
  576.     UINT64 begin;  
  577.     UINT64 end;  
  578.     begin = GetTimeM();  
  579.     UpBottomMergeSort(pDataArray, length);  
  580.     end = GetTimeM();  
  581.   
  582.     fprintf(fp, " %d"int(end-begin));  
  583.   
  584.     if (!CheckOrder(pDataArray, length))  
  585.         printf("UpBottomMergeSort algorithm failed!\n");  
  586.     else  
  587.         printf("UpBottomMergeSort algorithm succeed!\n");  
  588. }  
  589.   
  590. void QuickSortTest(int *pDataArray,int length, FILE *fp)  
  591. {  
  592.     //初始化数组  
  593.     for (int i = 0; i < length; i++)  
  594.         pDataArray[i] = rand()%100000;  
  595.   
  596.     UINT64 begin;  
  597.     UINT64 end;  
  598.     begin = GetTimeM();  
  599.     QuickSort(pDataArray, length);  
  600.     end = GetTimeM();  
  601.   
  602.     fprintf(fp, " %d"int(end-begin));  
  603.   
  604.     if (!CheckOrder(pDataArray, length))  
  605.         printf("QuickSort algorithm failed!\n");  
  606.     else  
  607.         printf("QuickSort algorithm succeed!\n");  
  608. }  
  609.   
  610. void HeapSortTest(int *pDataArray,int length, FILE *fp)  
  611. {  
  612.     //初始化数组  
  613.     for (int i = 0; i < length; i++)  
  614.         pDataArray[i] = rand()%100000;  
  615.   
  616.     UINT64 begin;  
  617.     UINT64 end;  
  618.     begin = GetTimeM();  
  619.     HeapSort(pDataArray, length);  
  620.     end = GetTimeM();  
  621.   
  622.     fprintf(fp, " %d"int(end-begin));  
  623.   
  624.     if (!CheckOrder(pDataArray, length))  
  625.         printf("HeapSort algorithm failed!\n");  
  626.     else  
  627.         printf("HeapSort algorithm succeed!\n");  
  628. }  
  629.   
  630. void RadixSortTest(int *pDataArray,int length, FILE *fp)  
  631. {  
  632.     //初始化数组  
  633.     for (int i = 0; i < length; i++)  
  634.         pDataArray[i] = rand()%100000;  
  635.   
  636.     UINT64 begin;  
  637.     UINT64 end;  
  638.     begin = GetTimeM();  
  639.     RadixSort(pDataArray, length);  
  640.     end = GetTimeM();  
  641.   
  642.     fprintf(fp, " %d"int(end-begin));  
  643.   
  644.     if (!CheckOrder(pDataArray, length))  
  645.         printf("RadixSort algorithm failed!\n");  
  646.     else  
  647.         printf("RadixSort algorithm succeed!\n");  
  648. }  
  649.   
  650. void ShellSortTest(int *pDataArray,int length, FILE *fp)  
  651. {  
  652.     //初始化数组  
  653.     for (int i = 0; i < length; i++)  
  654.         pDataArray[i] = rand()%100000;  
  655.   
  656.     UINT64 begin;  
  657.     UINT64 end;  
  658.     begin = GetTimeM();  
  659.     ShellSort(pDataArray, length);  
  660.     end = GetTimeM();  
  661.   
  662.     fprintf(fp, " %d"int(end-begin));  
  663.   
  664.     if (!CheckOrder(pDataArray, length))  
  665.         printf("ShellSort algorithm failed!\n");  
  666.     else  
  667.         printf("ShellSort algorithm succeed!\n");  
  668. }  
  669.   
  670. int main()  
  671. {  
  672. #define ARRAYLENGTH 10000    //无序数组初始长度  
  673. #define ADDLENGTH 10000    //无序数组增幅  
  674. #define MAXLENGTH 100000   //最大无序数组长度  
  675.   
  676.     int length;  
  677.     srand(time(NULL));  
  678.     //获取时钟频率  
  679.     LARGE_INTEGER litmp;  
  680.     QueryPerformanceFrequency(&litmp);  
  681.     time_fre = (UINT64 )litmp.QuadPart;  
  682.   
  683.     int *pDataArray = new int[MAXLENGTH];  
  684.     FILE *fp = fopen("data.txt""w");    //将结果存储与data.txt文件中;  
  685.                                           //每一行代表一种排序在不同数据规模下的时间(毫秒)  
  686.   
  687.     length = ARRAYLENGTH;  
  688.     for (; length <= MAXLENGTH; length += ADDLENGTH)  
  689.     {         
  690.         BubbleSortTest(pDataArray, length, fp);  
  691.     }  
  692.     fprintf(fp, "\n");  
  693.   
  694.     length = ARRAYLENGTH;  
  695.     for (; length <= MAXLENGTH; length += ADDLENGTH)  
  696.     {         
  697.         SelectSortTest(pDataArray, length, fp);  
  698.     }  
  699.     fprintf(fp, "\n");  
  700.   
  701.     length = ARRAYLENGTH;  
  702.     for (; length <= MAXLENGTH; length += ADDLENGTH)  
  703.     {         
  704.         InsertSortTest(pDataArray, length, fp);  
  705.     }  
  706.     fprintf(fp, "\n");  
  707.   
  708.     length = ARRAYLENGTH;  
  709.     for (; length <= MAXLENGTH; length += ADDLENGTH)  
  710.     {         
  711.         BottomUpMergeSortTest(pDataArray, length, fp);  
  712.     }  
  713.     fprintf(fp, "\n");  
  714.   
  715.     length = ARRAYLENGTH;  
  716.     for (; length <= MAXLENGTH; length += ADDLENGTH)  
  717.     {         
  718.         UpBottomMergeSortTest(pDataArray, length, fp);  
  719.     }  
  720.     fprintf(fp, "\n");  
  721.   
  722.     length = ARRAYLENGTH;  
  723.     for (; length <= MAXLENGTH; length += ADDLENGTH)  
  724.     {         
  725.         QuickSortTest(pDataArray, length, fp);  
  726.     }  
  727.     fprintf(fp, "\n");  
  728.   
  729.     length = ARRAYLENGTH;  
  730.     for (; length <= MAXLENGTH; length += ADDLENGTH)  
  731.     {         
  732.         HeapSortTest(pDataArray, length, fp);  
  733.     }  
  734.     fprintf(fp, "\n");  
  735.   
  736.     length = ARRAYLENGTH;  
  737.     for (; length <= MAXLENGTH; length += ADDLENGTH)  
  738.     {         
  739.         RadixSortTest(pDataArray, length, fp);  
  740.     }  
  741.     fprintf(fp, "\n");  
  742.   
  743.     length = ARRAYLENGTH;  
  744.     for (; length <= MAXLENGTH; length += ADDLENGTH)  
  745.     {         
  746.         ShellSortTest(pDataArray, length, fp);  
  747.     }  
  748.     fprintf(fp, "\n");  
  749.   
  750.     fclose(fp);  
  751.     free(pDataArray);  
  752.     return 0;  
  753. }  

ZT 9种排序

上一篇:测试简书的Markdown支持


下一篇:Same Tree