代码支持运行环境visual studio 2013。 我在Dev c++上运行不了，好像是timeGetTime()函数的问题，报错：\collect2.exe [Error] ld returned 1 exit status 代码写了多种排序算法，并进行了时间比较。由于基数排序消耗空间大，所以如果想使数组长度（ARRLEN）增大,最好现将基数排序相关代码注释掉，否则如果数组长度过大，会出现报错。 1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #pragma comment(lib, "Winmm.lib") 9 #define ARRLEN 10 10 /* run this program using the console pauser or add your own getch, system("pause") or input loop */ 11 void printArr(int arr[], int len){ 12 for(int i = 0; i < len; ++i) 13 printf("%d\t", arr[i]); 14 printf("\n"); 15 } 16 //***************************************选择排序******************************* 17 void Select_Sort(int arr[], int length){ 18 int temp; 19 for(int i = 0; i < length - 1; ++i){ 20 for(int j = i + 1; j < length; ++j){ 21 if(arr[i] > arr[j]){ 22 temp = arr[i]; 23 arr[i] = arr[j]; 24 arr[j] = temp; 25 } 26 } 27 } 28 } 29 30 //**********************************************冒泡排序********************************** 31 void Bubble_Sort(int arr[], int length){ 32 int temp; 33 for(int i = 0; i < length - 1; ++i){ 34 for(int j = 0; j < length - 1 - i; ++j){ 35 if(arr[j] > arr[j + 1]){ 36 temp = arr[j]; 37 arr[j] = arr[j + 1]; 38 arr[j + 1] = temp; 39 } 40 } 41 } 42 } 43 //***********************************************快速排序********************************* 44 int part(int arr[], int begin, int end){ //将待排序数组分成两部分，左边的部分均小于右边部分 45 int k = begin; 46 for(int i = begin + 1; i <= end; ++i){ 47 if(arr[i] < arr[k]){ 48 int temp = arr[i]; 49 for(int j = i; j > k; --j){ 50 arr[j] = arr[j - 1]; 51 } 52 arr[k] = temp; 53 k--; 54 } 55 } 56 return k; 57 } 58 void _Quick_Sort(int arr[], int begin, int end){ 59 if(begin >= end) return; 60 int k = part(arr, begin, end);//获取中间值 61 _Quick_Sort(arr, begin, k - 1); 62 _Quick_Sort(arr, k + 1, end); 63 } 64 void Quick_Sort(int arr[], int len){ 65 _Quick_Sort(arr, 0, len - 1); 66 } 67 68 //*********************************************插入排序************************************* 69 void Insert_Sort(int arr[], int len){ 70 int tempVal; 71 int j;//下标 72 for(int i = 1; i < len; ++i){ 73 tempVal = arr[i]; 74 j = i - 1; 75 while(j >= 0 && arr[j] > tempVal){ 76 arr[j + 1] = arr[j]; 77 --j; 78 } 79 arr[j + 1] = tempVal; 80 } 81 } 82 //***********************************************希尔排序 **************************************** 83 void Shell_Sort(int arr[], int len){ 84 int tempVal; 85 int j; 86 int jump;//步长值 87 jump = len >> 1; 88 while(jump != 0){ 89 for(int i = jump; i < len; ++i){ 90 tempVal = arr[i]; 91 j = i - jump; 92 while(j >= 0 && arr[j] > tempVal){ 93 arr[j + jump] = arr[j]; 94 j -= jump; 95 } 96 arr[j + jump] = tempVal; 97 } 98 jump >>= 1; 99 }100 } 101 //*****************************基数排序（桶排序）不通过比较来排序， 对整数的排序时间最短，但空间最浪费 ******102 void Radix_Sort(int arr[], int len){103 for(int n = 1; n <= 1000; n *= 10){ //n代表整数的位数 104 int temp[10][10] = {}; //辅助数组 105 for(int i = 0; i < 10; ++i){106 for(int j = 0; j < 10; ++j){107 temp[i][j] = -1;108 }109 }110 for(int i = 0; i < len; ++i){ //把待排序数组里的元素按规律放在对应的辅助数组里面 111 int m = (arr[i] / n) % 10;112 temp[m][i] = arr[i];113 }114 int k = 0;115 for(int i = 0; i < 10; ++i){ //把辅助数组的数据重新放回排序数组 116 for(int j = 0; j < 10; ++j){117 if(temp[i][j] != -1){118 arr[k++] = temp[i][j];119 }120 }121 }122 }123 } 124 //**********************************************堆排序*************************************125 126 //堆调整127 void Heap_Adjust(int arr[], int basic, int len){128 int temp = arr[basic];129 int child = 2 * basic + 1;//左孩子节点位置130 while(child < len){131 if(child + 1 < len && arr[child] < arr[child + 1]){ //如果有右孩子且有孩子大于左孩子，则用有孩子比较 132 ++child;133 }134 if(arr[basic] < arr[child]){ //如果较大子节点大于父节点 135 arr[basic] = arr[child];//较大子节点上移，替换父节点 136 basic = child; //重新设置父节点位置 137 child = 2 * basic + 1;//重置子节点位置 138 }139 else{140 break;141 }142 arr[basic] = temp;143 } 144 145 } 146 //创建初始堆 147 void Build_Heap(int arr[], int length){148 //最后一个有孩子的节点位置 i = (length - 1) / 2149 for(int i = (length - 1) / 2; i >= 0; --i)150 Heap_Adjust(arr, i, length);151 } 152 void Heap_Sort(int arr[], int len){153 Build_Heap(arr, len); //初始堆 154 for(int i = len - 1; i > 0; --i){155 int temp = arr[i];156 arr[i] = arr[0];157 arr[0] = temp;158 Heap_Adjust(arr, 0, i);159 }160 } 161 //****************************************************归并排序*******************************162 void _merge_in_arr(int arr[], int left, int mid, int right){163 //首先得有一个辅助数组164 int length = right - left + 1;//元素个数比下标差值要多一165 int *pData = new int[length];166 memset(pData, 0, sizeof(int)* length) ;//给辅助数组内存清0值167 168 int low = left;//定义一个辅助变量，防止修改left169 int hig = mid + 1;170 int index = 0;//pData的索引171 172 while(hig <= right){ //右边的合并是否完成，没有完成,循环173 while(arr[low] <= arr[hig] && low <= mid){ //如果左边的值小于右边的值且左边没有越界174 pData[index] = arr[low];175 low++;176 index++;177 }178 if(low > mid) break;//证明左边已经放完，只剩下右边的数没有合并179 while(arr[low] > arr[hig] && hig <= right){ //如果右边的值小于左边的值且右边没有越界180 pData[index] = arr[hig];181 hig++;182 index++;183 }184 }185 //到这一步，一边已经放完186 //左边没有放完187 if(low <= mid) memmove(&pData[index], &arr[low], sizeof(int)* (mid - low + 1));188 //右边没有放完189 if(hig <= right) memmove(&pData[index], &arr[hig], sizeof(int)* (right - hig + 1));190 memmove(&arr[left], pData, sizeof(int) * length);//把pDate数据拷贝回a数组191 delete[] pData;192 }193 194 void _merge(int arr[], int left, int right){195 if(left >= right) return;196 int mid = (left + right) >> 1;//求中间值 197 _merge(arr, 0, mid);//拆左边198 _merge(arr, mid + 1, right);//拆右边199 _merge_in_arr(arr, left, mid, right);//前两步递归操作，下一步合并200 }201 //归并排序 分而治之202 void Merge_Sort(int arr[], int len){203 _merge(arr, 0, len - 1);204 } 205 206 void Print(int arr[], int len){207 for(int i = 0; i < len; ++i)208 printf("%d\t", arr[i]);209 printf("\n");210 }211 int main(int argc, char** argv) {212 srand((unsigned int)time(NULL));213 int arrSelect[ARRLEN], arrBubble[ARRLEN], arrQuick[ARRLEN], arrInsert[ARRLEN], arrShell[ARRLEN], arrRadix[ARRLEN], 214 arrHeap[ARRLEN], arrMerge[ARRLEN];215 for(int i = 0; i < ARRLEN; ++i){216 arrSelect[i] = rand() % 100;217 arrBubble[i] = rand() % 100;218 arrQuick[i] = rand() % 100;219 arrInsert[i] = rand() % 100;220 arrShell[i] = rand() % 100;221 arrRadix[i] = rand() % 100;222 arrHeap[i] = rand() % 100;223 arrMerge[i] = rand() % 100;224 }225 printf("===============================排序前=========================\n");226 printf("选择排序：");Print(arrSelect, ARRLEN);227 printf("冒泡排序：");Print(arrBubble, ARRLEN);228 printf("快速排序：");Print(arrQuick, ARRLEN);229 printf("插入排序：");Print(arrInsert, ARRLEN);230 printf("希尔排序：");Print(arrShell, ARRLEN);231 printf("基数排序：");Print(arrRadix, ARRLEN);232 printf("堆排序 ：");Print(arrHeap, ARRLEN);233 printf("归并排序：");Print(arrMerge, ARRLEN);234 printf("===============================排序后=========================\n");235 srand(timeGetTime());236 237 float beginTimer = timeGetTime() / 1000.0f;238 Select_Sort(arrSelect, ARRLEN);239 float endTimer = timeGetTime() / 1000.0f;240 printf("选择排序： 耗时 = %f", endTimer - beginTimer);Print(arrSelect, ARRLEN);241 242 beginTimer = timeGetTime() / 1000.0f;243 Bubble_Sort(arrBubble, ARRLEN);244 endTimer = timeGetTime() / 1000.0f;245 printf("冒泡排序： 耗时 = %f", endTimer - beginTimer);Print(arrBubble, ARRLEN);246 247 beginTimer = timeGetTime() / 1000.0f;248 Quick_Sort(arrQuick, ARRLEN);249 endTimer = timeGetTime() / 1000.0f;250 printf("快速排序： 耗时 = %f", endTimer - beginTimer);Print(arrQuick, ARRLEN);251 252 beginTimer = timeGetTime() / 1000.0f;253 Insert_Sort(arrInsert, ARRLEN);254 endTimer = timeGetTime() / 1000.0f;255 printf("插入排序： 耗时 = %f", endTimer - beginTimer);Print(arrInsert, ARRLEN);256 257 beginTimer = timeGetTime() / 1000.0f;258 Shell_Sort(arrShell, ARRLEN);259 endTimer = timeGetTime() / 1000.0f;260 printf("希尔排序： 耗时 = %f", endTimer - beginTimer);Print(arrShell, ARRLEN);261 262 beginTimer = timeGetTime() / 1000.0f;263 Radix_Sort(arrRadix, ARRLEN);264 endTimer = timeGetTime() / 1000.0f;265 printf("基数排序： 耗时 = %f", endTimer - beginTimer);Print(arrRadix, ARRLEN);266 267 beginTimer = timeGetTime() / 1000.0f;268 Heap_Sort(arrHeap, ARRLEN);269 endTimer = timeGetTime() / 1000.0f;270 printf("堆排序 ： 耗时 = %f", endTimer - beginTimer);Print(arrHeap, ARRLEN);271 272 beginTimer = timeGetTime() / 1000.0f;273 Merge_Sort(arrMerge, ARRLEN);274 endTimer = timeGetTime() / 1000.0f;275 printf("归并排序： 耗时 = %f", endTimer - beginTimer);Print(arrMerge, ARRLEN);276 return 0;277 }