C语言排序算法实现：冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序、堆排序、计数排序

ゝ一世哀愁。 2022-10-27 01:41 173阅读 0赞

--------------------

C语言实现各排序算法：冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序、堆排序、计数排序（原创内容，禁止转载）

--------------------

### 1.引入所需头文件 ###

#include <stdio.h>
    #include <malloc.h> #动态申请内存
    #include <stdlib.h>
    #include <time.h>
    #include <sys/timeb.h>
    #include <string.h>

### 2.函数声明 ###

int* makeData(int total, int m, int n);//生成一个含有total个介于m和n之间的无序数的数组
    long long getTimeStamp();//读取当前毫秒时间
    //测试一个排序算法函数
    int testOneSortFunc(char* funName, char* textName, int* arr, int len , bool mode, bool isPrintArrData);
    int testSort(int total, bool isPrintArrData);//测试所有排序算法
    void printArrData(int* arr, int len);//打印数组中的数据
    int getRandNum(int m, int n);//获取一个m-n之间的随机数（包括m和n）
    
    void bubbleSort(int* arr, int len, bool mode);//冒泡排序
    void insertionSort(int* arr, int len, bool mode);//插入排序
    void selectionSort(int* arr, int len, bool mode);//选择排序
    void mergeSort(int* arr, int start, int end, bool mode);//归并排序
    void quickSort(int* arr, int start, int end, bool mode);//快速排序
    void shellSort(int* arr, int len, bool mode);//希尔排序
    void heapSort(int* arr, int len, bool mode);//堆排序
    void heapNodeSink(int* arr, int len, int nodeNo, bool mode);//堆节点元素下沉操作函数
    void countingSort(int* arr, int len, bool mode);//计数排序

### 3.计数排序 ###

//计数排序
    //author：Hengda
    //arr：待排序数组
    //len：数组元素个数
    //mode：true为倒序，false为正序
    void countingSort( int * arr, int len, bool mode) { 
    	int i, j, pos=0, temp;
    	int min = arr[0], max = arr[0];//数组中的最大值和最小值
    	int* countArr = NULL;//统计数组
    	int countArrLen = 0;//统计数组的长度
    
    	//查找最小值
    	min = arr[0];
    	max = arr[0];
    	for (i = 0; i < len; i++) { 
    		if (arr[i] > max) max = arr[i];
    		if (arr[i] < min) min = arr[i];
    	}
    	//申请统计数组所需内存空间
    	countArrLen = max - min + 1;
    	countArr = ( int* )malloc(countArrLen * sizeof(int) );
    	
    	//全部初始化为0
    	memset( countArr, 0, countArrLen * sizeof(int));
    	
    	//统计
    	for (i = 0; i < len; i++) { 
    		temp = arr[i] - min;
    		countArr[temp]++;
    	}
    	
    	//回填
    	pos = 0;
    	if (mode) { 
    		//倒序回填到arr数组
    		for (i = countArrLen-1; i >=0; i--) { 
    			for (j = 0; j < countArr[i]; j++) { 
    				arr[pos++] = i + min;
    			}
    		}
    	}else { 
    		//正序回填到arr数组
    		for (i = 0; i < countArrLen; i++) { 
    			for (j = 0; j < countArr[i]; j++) { 
    				arr[pos++] = i + min;
    			}
    		}
    	}
    	//统计数组使用完毕，释放统计数组所占用的内存
    	free(countArr);
    	countArr = NULL;
    }

### 4.堆排序 ###

//堆排序
    //author：Hengda
    //arr：待排序数组
    //len：数组元素个数
    //mode：true为倒序，false为正序
    void heapSort(int * arr, int len, bool mode) { 
    	int i, j, temp;
    	//使数组满足二叉堆性质，即父节点总大于等于或者小于等于子节点
    	int lastFatherNo = len / 2 - 1;
    	for (i = lastFatherNo; i >= 0; i-- ) { 
    		heapNodeSink(arr, len, i, mode);
    	}
    	//依次交换堆顶和堆尾元素值，每次交换完，将堆长度减1，并且重新下沉堆顶元素
    	for (i = len - 1; i > 0; i-- ) { 
    		//交换堆顶和堆尾元素
    		temp = arr[0];
    		arr[0] = arr[i];
    		arr[i] = temp;
    		heapNodeSink(arr, i, 0, mode);
    	}
    }
    //二叉堆节点下沉操作函数
    //author：Hengda
    //arr：待排序数组
    //len：数组元素个数
    //nodeNo：当前下沉节点下标（序号）
    //mode：true为倒序，false为正序
    void heapNodeSink(int * arr, int len, int nodeNo, bool mode) { 
    	int temp;
    	int lChild = (nodeNo + 1) * 2 - 1;//左孩子序号
    	int rChild = lChild + 1;//右孩子序号
    	int minMaxNo = nodeNo;//初始化最大或最小标记
    	//标记左孩子为最大或最小
    	if (lChild < len) { 
    		if (mode ? arr[lChild] < arr[minMaxNo] : arr[lChild] > arr[minMaxNo]) { 
    			minMaxNo = lChild;//标记位左孩子
    		}
    	}
    	//标记右孩子为最大或最小
    	if (rChild < len) { 
    		if (mode ? arr[rChild] < arr[minMaxNo] : arr[rChild] > arr[minMaxNo]) { 
    			minMaxNo = rChild;//标记位右孩子
    		}
    	}
    	//当前节点与最大或最小标记节点值进行交换
    	if (minMaxNo != nodeNo) { 
    		temp = arr[ nodeNo ];
    		arr[nodeNo] = arr[minMaxNo];
    		arr[minMaxNo] = temp;
    		//继续下沉
    		heapNodeSink(arr, len, minMaxNo, mode);
    	}
    }

### 5.希尔排序 ###

//希尔排序
    //author：Hengda
    //arr：待排序数组
    //len：数组元素个数
    //mode：true为倒序，false为正序
    void shellSort(int * arr, int len, bool mode) { 
    	int i, j, temp, gap = 1;
    	//计算合理的数据分组间隙大小
    	while ( gap < len/5 ) { 
    		gap = gap * 5 + 1;
    	}
    	//逐渐收缩间隙值，并对每个分组方案进行插入排序
    	do{ 
    		//以下为插入排序算法，元素与元素间隔为gap
    		for (i = gap; i < len; i++) { 
    			temp = arr[i];
    			for (j = i - gap; j >= 0 && ( mode ? arr[j] < temp : arr[j] > temp );j-=gap) { 
    				arr[j + gap] = arr[j];//向后移动
    			}
    			arr[j + gap] = temp;
    		}
    	} while ( gap = ( gap / 5) );//搜索间隙值
    }

### 6.快速排序 ###

//快速排序
    //author：Hengda
    //arr：待排序数组
    //start：待排序数据段的起始下标（序号），含
    //end：待排序数据款的末尾下标（序号），含
    //mode：true为倒序，false为正序
    void quickSort( int * arr, int start, int end, bool mode ) { 
    	int i, temp, divValue , pos;
    	
    	if(start < end){ 
    		divValue = arr[end];//初始分界为当前数据段的末尾元素
    		pos = start;
    		//将小于等于或者大于等于分界值得元素值依次从左往右排列
    		for (i = start; i <= end; i++) { 
    			if (mode ? arr[i] >= divValue : arr[i] <= divValue) { 
    				//交换
    				temp = arr[pos];
    				arr[pos] = arr[i];
    				arr[i] = temp;
    				pos++;
    			}
    		}
    		pos--;//pos为分界元素下标
    		if (start < pos) quickSort(arr, start, pos - 1, mode);//排序左侧数据段
    		if (pos < end) quickSort(arr, pos + 1, end, mode);//排序右侧数据段
    	}
    	//return arr;
    }

### 7.归并排序 ###

//归并排序
    //author：Hengda
    //arr：待排序数组
    //start：待排序数据段的起始下标（序号），含
    //end：待排序数据款的末尾下标（序号），含
    //mode：true为倒序，false为正序
    void mergeSort( int * arr, int start, int end, bool mode ) { 
    	int i, j, temp, div, left;
    
    	//分成两段分别排序
    	if ( end - start > 4 ) { 
    		div = start + (end - start) / 2;
    		mergeSort(arr, start, div, mode);//排序左侧数据段
    		mergeSort(arr, div + 1, end, mode);//排序右侧数据段
    	}
    
    	//对两段组成的整段排序，以下为插入排序逻辑
    	for (i = start + 1; i <= end; i++) { 
    		temp = arr[i];
    		for (j = i - 1; j >= 0 && (mode ? arr[j] < temp : arr[j] > temp); j--) { 
    			arr[j + 1] = arr[j];//向后移动
    		}
    		arr[j + 1] = temp;
    	}
    	//return arr;
    }

### 8.选择排序 ###

//选择排序
    //author：Hengda
    //arr：待排序数组
    //len：数组元素个数
    //mode：true为倒序，false为正序
    void selectionSort( int * arr, int len, bool mode ) { 
    	//
    	int i, j, temp, minMaxNo;
    	//依次从原数组中，除了当前待处理位置之前的元素外，剩余元素中找到最大或者最小的值，将此值与当前待处理元素相交换
    	for (i = 0; i < len - 1; i++) { 
    		minMaxNo = i;
    		//剩余元素中查找
    		for (j = i + 1; j < len; j++) { 
    			if ( mode ? arr[ j ] > arr[minMaxNo] : arr[ j ] < arr[minMaxNo] ) { 
    				minMaxNo = j;//标记查找到的最大或者最小元素下标
    			}
    		}
    		//交换
    		temp = arr[i];
    		arr[ i ] = arr[ minMaxNo ];
    		arr[ minMaxNo ] = temp;
    	}
    	//return arr;
    }

### 9.插入排序 ###

//插入排序
    //author：Hengda
    //arr：待排序数组
    //len：数组元素个数
    //mode：true为倒序，false为正序
    void insertionSort( int *arr, int len, bool mode ) { 
    	//
    	int i, j, temp;
    	//从左向右依次处理，每个元素依次向前比较，如果比前面的大或者小则与其交换，并继续向前比较，直到遇到大于或者等于其前面的数为止。
    	for ( i = 1; i < len; i++ ) { 
    		temp = arr[ i ];
    		for ( j = i - 1; j >= 0 && ( mode ? arr[ j ] < temp : arr[j] > temp ); j-- ) { 
    			arr[j + 1] = arr[ j ];//向后移动
    		}
    		arr[j + 1] = temp;
    	}
    	//return arr;
    }

### 10.冒泡排序 ###

//冒泡排序
    //author：Hengda
    //arr：待排序数组
    //len：数组元素个数
    //mode：true为倒序，false为正序
    void bubbleSort( int *arr, int len, bool mode ){ 
    	int i, j, temp;
    	//阶梯式从0下标元素开始向后冒泡（交换）两两比较中的最大值或者最小值
    	for (i = 0; i < len - 1; i++) { 
    		for (j = 0; j < len - 1 - i; j++ ) { 
    			//比较
    			if ( mode ? arr[j] < arr[j + 1] : arr[ j ] > arr[ j+1 ] ) { 
    				//交换
    				temp = arr[j];
    				arr[j] = arr[j+1];
    				arr[j + 1] = temp;
    			}
    		}
    	}
    	//return arr;
    }

### 11.测试排序10万个无序数 ###

//主函数
    int main( int argc, char* argv[] ){ 
    	char ch;
    	//测试排序10万个无序数
    	testSort(100000, true);
    	
    	printf("\r\n请按任意键退出\r\n\r\n");
    	scanf_s("%c", &ch);
    	exit(0);
    }

#### 排序结果 ####

原始数据：
    99740 56491 28053 74649 30237 68551 62548 94002 19459 3962 93348 45085 82172 74158 5175 99287 5320 75844 29583 42701 88924 86046 63591 27515 19477 18705 67385 33678 69946 71351 30980 59802 11237 73866 36095 80482 12368 74496 94802 415 49829 99711 9069 31700 87688 30845 15987 29480 20145 19187 46647 42448 87393 38340 23478 44059 45805 30852 86599 58623 39440 17162 51569 28356 54725 36710 50864 99114 67634 10941 25105 94587 22676 26529 15148 34439 95556 8977 63803 97261 86946 40680 55786 25987 44505 95053 25590 6479 95831 93570 57441 72294 93558 81940 12464 37003 74932 92007 23261 33296 .........47539 57188 7798 71435 11089 30560 66178 98644 33367 95957 13289 49019 19494 45251 41117 82950 92950 9197 44658 23345 3631 22339 64421 38820 56242 69418 92756 47435 56287 41178 67019 8405 73397 56222 53235 80403 80725 85829 47564 64201 81839 39265 3433 67566 9419 63031 40698 60505 68622 24796 61420 72752 74176 78875 46951 93657 47632 97783 43329 81299 31434 13833 43946 1376 67806 45064 36668 42223 73084 97155 21543 65654 89718 78680 31286 38536 11380 43232 68681 7689 6165 82877 34957 34155 87407 65802 41922 67107 58573 27486 22986 90879 54227 69817 58365 34127 51219 24571 79762 12226
    ---------------
    
    
    冒泡排序-正序耗时：43491 毫秒
    
    1 1 1 5 8 9 11 12 12 12 13 13 13 13 13 15 16 18 19 19 20 22 23 23 23 24 25 27 29 30 31 33 33 34 35 36 39 39 40 42 42 44 44 45 45 45 45 46 47 49 50 52 52 53 57 57 58 58 59 60 61 62 63 64 65 65 65 66 67 67 67 67 72 72 73 73 74 75 75 76 78 78 79 80 80 83 84 84 85 85 87 87 88 90 90 91 92 92 93 93 .........99907 99907 99908 99909 99909 99909 99911 99912 99912 99913 99914 99916 99916 99916 99918 99919 99920 99920 99921 99922 99925 99927 99929 99929 99930 99933 99934 99936 99937 99938 99938 99939 99942 99943 99943 99944 99945 99945 99946 99947 99947 99947 99951 99951 99953 99953 99953 99953 99955 99955 99955 99955 99956 99957 99958 99958 99958 99959 99959 99965 99965 99966 99968 99969 99969 99970 99973 99974 99974 99974 99975 99975 99979 99979 99979 99980 99982 99984 99984 99984 99984 99984 99985 99985 99987 99988 99988 99988 99992 99993 99993 99994 99996 99996 99997 99997 99998 99999 99999 99999
    
    冒泡排序-倒序耗时：43409 毫秒
    
    99999 99999 99999 99998 99997 99997 99996 99996 99994 99993 99993 99992 99988 99988 99988 99987 99985 99985 99984 99984 99984 99984 99984 99982 99980 99979 99979 99979 99975 99975 99974 99974 99974 99973 99970 99969 99969 99968 99966 99965 99965 99959 99959 99958 99958 99958 99957 99956 99955 99955 99955 99955 99953 99953 99953 99953 99951 99951 99947 99947 99947 99946 99945 99945 99944 99943 99943 99942 99939 99938 99938 99937 99936 99934 99933 99930 99929 99929 99927 99925 99922 99921 99920 99920 99919 99918 99916 99916 99916 99914 99913 99912 99912 99911 99909 99909 99909 99908 99907 99907 .........93 93 92 92 91 90 90 88 87 87 85 85 84 84 83 80 80 79 78 78 76 75 75 74 73 73 72 72 67 67 67 67 66 65 65 65 64 63 62 61 60 59 58 58 57 57 53 52 52 50 49 47 46 45 45 45 45 44 44 42 42 40 39 39 36 35 34 33 33 31 30 29 27 25 24 23 23 23 22 20 19 19 18 16 15 13 13 13 13 13 12 12 12 11 9 8 5 1 1 1
    ---------------
    
    
    选择排序-正序耗时：15733 毫秒
    
    1 1 1 5 8 9 11 12 12 12 13 13 13 13 13 15 16 18 19 19 20 22 23 23 23 24 25 27 29 30 31 33 33 34 35 36 39 39 40 42 42 44 44 45 45 45 45 46 47 49 50 52 52 53 57 57 58 58 59 60 61 62 63 64 65 65 65 66 67 67 67 67 72 72 73 73 74 75 75 76 78 78 79 80 80 83 84 84 85 85 87 87 88 90 90 91 92 92 93 93 .........99907 99907 99908 99909 99909 99909 99911 99912 99912 99913 99914 99916 99916 99916 99918 99919 99920 99920 99921 99922 99925 99927 99929 99929 99930 99933 99934 99936 99937 99938 99938 99939 99942 99943 99943 99944 99945 99945 99946 99947 99947 99947 99951 99951 99953 99953 99953 99953 99955 99955 99955 99955 99956 99957 99958 99958 99958 99959 99959 99965 99965 99966 99968 99969 99969 99970 99973 99974 99974 99974 99975 99975 99979 99979 99979 99980 99982 99984 99984 99984 99984 99984 99985 99985 99987 99988 99988 99988 99992 99993 99993 99994 99996 99996 99997 99997 99998 99999 99999 99999
    
    选择排序-倒序耗时：15330 毫秒
    
    99999 99999 99999 99998 99997 99997 99996 99996 99994 99993 99993 99992 99988 99988 99988 99987 99985 99985 99984 99984 99984 99984 99984 99982 99980 99979 99979 99979 99975 99975 99974 99974 99974 99973 99970 99969 99969 99968 99966 99965 99965 99959 99959 99958 99958 99958 99957 99956 99955 99955 99955 99955 99953 99953 99953 99953 99951 99951 99947 99947 99947 99946 99945 99945 99944 99943 99943 99942 99939 99938 99938 99937 99936 99934 99933 99930 99929 99929 99927 99925 99922 99921 99920 99920 99919 99918 99916 99916 99916 99914 99913 99912 99912 99911 99909 99909 99909 99908 99907 99907 .........93 93 92 92 91 90 90 88 87 87 85 85 84 84 83 80 80 79 78 78 76 75 75 74 73 73 72 72 67 67 67 67 66 65 65 65 64 63 62 61 60 59 58 58 57 57 53 52 52 50 49 47 46 45 45 45 45 44 44 42 42 40 39 39 36 35 34 33 33 31 30 29 27 25 24 23 23 23 22 20 19 19 18 16 15 13 13 13 13 13 12 12 12 11 9 8 5 1 1 1
    ---------------
    
    
    插入排序-正序耗时：12006 毫秒
    
    1 1 1 5 8 9 11 12 12 12 13 13 13 13 13 15 16 18 19 19 20 22 23 23 23 24 25 27 29 30 31 33 33 34 35 36 39 39 40 42 42 44 44 45 45 45 45 46 47 49 50 52 52 53 57 57 58 58 59 60 61 62 63 64 65 65 65 66 67 67 67 67 72 72 73 73 74 75 75 76 78 78 79 80 80 83 84 84 85 85 87 87 88 90 90 91 92 92 93 93 .........99907 99907 99908 99909 99909 99909 99911 99912 99912 99913 99914 99916 99916 99916 99918 99919 99920 99920 99921 99922 99925 99927 99929 99929 99930 99933 99934 99936 99937 99938 99938 99939 99942 99943 99943 99944 99945 99945 99946 99947 99947 99947 99951 99951 99953 99953 99953 99953 99955 99955 99955 99955 99956 99957 99958 99958 99958 99959 99959 99965 99965 99966 99968 99969 99969 99970 99973 99974 99974 99974 99975 99975 99979 99979 99979 99980 99982 99984 99984 99984 99984 99984 99985 99985 99987 99988 99988 99988 99992 99993 99993 99994 99996 99996 99997 99997 99998 99999 99999 99999
    
    插入排序-倒序耗时：8730 毫秒
    
    99999 99999 99999 99998 99997 99997 99996 99996 99994 99993 99993 99992 99988 99988 99988 99987 99985 99985 99984 99984 99984 99984 99984 99982 99980 99979 99979 99979 99975 99975 99974 99974 99974 99973 99970 99969 99969 99968 99966 99965 99965 99959 99959 99958 99958 99958 99957 99956 99955 99955 99955 99955 99953 99953 99953 99953 99951 99951 99947 99947 99947 99946 99945 99945 99944 99943 99943 99942 99939 99938 99938 99937 99936 99934 99933 99930 99929 99929 99927 99925 99922 99921 99920 99920 99919 99918 99916 99916 99916 99914 99913 99912 99912 99911 99909 99909 99909 99908 99907 99907 .........93 93 92 92 91 90 90 88 87 87 85 85 84 84 83 80 80 79 78 78 76 75 75 74 73 73 72 72 67 67 67 67 66 65 65 65 64 63 62 61 60 59 58 58 57 57 53 52 52 50 49 47 46 45 45 45 45 44 44 42 42 40 39 39 36 35 34 33 33 31 30 29 27 25 24 23 23 23 22 20 19 19 18 16 15 13 13 13 13 13 12 12 12 11 9 8 5 1 1 1
    ---------------
    
    
    归并排序-正序耗时：8837 毫秒
    
    1 1 1 5 8 9 11 12 12 12 13 13 13 13 13 15 16 18 19 19 20 22 23 23 23 24 25 27 29 30 31 33 33 34 35 36 39 39 40 42 42 44 44 45 45 45 45 46 47 49 50 52 52 53 57 57 58 58 59 60 61 62 63 64 65 65 65 66 67 67 67 67 72 72 73 73 74 75 75 76 78 78 79 80 80 83 84 84 85 85 87 87 88 90 90 91 92 92 93 93 .........99907 99907 99908 99909 99909 99909 99911 99912 99912 99913 99914 99916 99916 99916 99918 99919 99920 99920 99921 99922 99925 99927 99929 99929 99930 99933 99934 99936 99937 99938 99938 99939 99942 99943 99943 99944 99945 99945 99946 99947 99947 99947 99951 99951 99953 99953 99953 99953 99955 99955 99955 99955 99956 99957 99958 99958 99958 99959 99959 99965 99965 99966 99968 99969 99969 99970 99973 99974 99974 99974 99975 99975 99979 99979 99979 99980 99982 99984 99984 99984 99984 99984 99985 99985 99987 99988 99988 99988 99992 99993 99993 99994 99996 99996 99997 99997 99998 99999 99999 99999
    
    归并排序-倒序耗时：8610 毫秒
    
    99999 99999 99999 99998 99997 99997 99996 99996 99994 99993 99993 99992 99988 99988 99988 99987 99985 99985 99984 99984 99984 99984 99984 99982 99980 99979 99979 99979 99975 99975 99974 99974 99974 99973 99970 99969 99969 99968 99966 99965 99965 99959 99959 99958 99958 99958 99957 99956 99955 99955 99955 99955 99953 99953 99953 99953 99951 99951 99947 99947 99947 99946 99945 99945 99944 99943 99943 99942 99939 99938 99938 99937 99936 99934 99933 99930 99929 99929 99927 99925 99922 99921 99920 99920 99919 99918 99916 99916 99916 99914 99913 99912 99912 99911 99909 99909 99909 99908 99907 99907 .........93 93 92 92 91 90 90 88 87 87 85 85 84 84 83 80 80 79 78 78 76 75 75 74 73 73 72 72 67 67 67 67 66 65 65 65 64 63 62 61 60 59 58 58 57 57 53 52 52 50 49 47 46 45 45 45 45 44 44 42 42 40 39 39 36 35 34 33 33 31 30 29 27 25 24 23 23 23 22 20 19 19 18 16 15 13 13 13 13 13 12 12 12 11 9 8 5 1 1 1
    ---------------
    
    
    堆排序-正序耗时：58 毫秒
    
    1 1 1 5 8 9 11 12 12 12 13 13 13 13 13 15 16 18 19 19 20 22 23 23 23 24 25 27 29 30 31 33 33 34 35 36 39 39 40 42 42 44 44 45 45 45 45 46 47 49 50 52 52 53 57 57 58 58 59 60 61 62 63 64 65 65 65 66 67 67 67 67 72 72 73 73 74 75 75 76 78 78 79 80 80 83 84 84 85 85 87 87 88 90 90 91 92 92 93 93 .........99907 99907 99908 99909 99909 99909 99911 99912 99912 99913 99914 99916 99916 99916 99918 99919 99920 99920 99921 99922 99925 99927 99929 99929 99930 99933 99934 99936 99937 99938 99938 99939 99942 99943 99943 99944 99945 99945 99946 99947 99947 99947 99951 99951 99953 99953 99953 99953 99955 99955 99955 99955 99956 99957 99958 99958 99958 99959 99959 99965 99965 99966 99968 99969 99969 99970 99973 99974 99974 99974 99975 99975 99979 99979 99979 99980 99982 99984 99984 99984 99984 99984 99985 99985 99987 99988 99988 99988 99992 99993 99993 99994 99996 99996 99997 99997 99998 99999 99999 99999
    
    堆排序-倒序耗时：50 毫秒
    
    99999 99999 99999 99998 99997 99997 99996 99996 99994 99993 99993 99992 99988 99988 99988 99987 99985 99985 99984 99984 99984 99984 99984 99982 99980 99979 99979 99979 99975 99975 99974 99974 99974 99973 99970 99969 99969 99968 99966 99965 99965 99959 99959 99958 99958 99958 99957 99956 99955 99955 99955 99955 99953 99953 99953 99953 99951 99951 99947 99947 99947 99946 99945 99945 99944 99943 99943 99942 99939 99938 99938 99937 99936 99934 99933 99930 99929 99929 99927 99925 99922 99921 99920 99920 99919 99918 99916 99916 99916 99914 99913 99912 99912 99911 99909 99909 99909 99908 99907 99907 .........93 93 92 92 91 90 90 88 87 87 85 85 84 84 83 80 80 79 78 78 76 75 75 74 73 73 72 72 67 67 67 67 66 65 65 65 64 63 62 61 60 59 58 58 57 57 53 52 52 50 49 47 46 45 45 45 45 44 44 42 42 40 39 39 36 35 34 33 33 31 30 29 27 25 24 23 23 23 22 20 19 19 18 16 15 13 13 13 13 13 12 12 12 11 9 8 5 1 1 1
    ---------------
    
    
    希尔排序-正序耗时：45 毫秒
    
    1 1 1 5 8 9 11 12 12 12 13 13 13 13 13 15 16 18 19 19 20 22 23 23 23 24 25 27 29 30 31 33 33 34 35 36 39 39 40 42 42 44 44 45 45 45 45 46 47 49 50 52 52 53 57 57 58 58 59 60 61 62 63 64 65 65 65 66 67 67 67 67 72 72 73 73 74 75 75 76 78 78 79 80 80 83 84 84 85 85 87 87 88 90 90 91 92 92 93 93 .........99907 99907 99908 99909 99909 99909 99911 99912 99912 99913 99914 99916 99916 99916 99918 99919 99920 99920 99921 99922 99925 99927 99929 99929 99930 99933 99934 99936 99937 99938 99938 99939 99942 99943 99943 99944 99945 99945 99946 99947 99947 99947 99951 99951 99953 99953 99953 99953 99955 99955 99955 99955 99956 99957 99958 99958 99958 99959 99959 99965 99965 99966 99968 99969 99969 99970 99973 99974 99974 99974 99975 99975 99979 99979 99979 99980 99982 99984 99984 99984 99984 99984 99985 99985 99987 99988 99988 99988 99992 99993 99993 99994 99996 99996 99997 99997 99998 99999 99999 99999
    
    希尔排序-倒序耗时：25 毫秒
    
    99999 99999 99999 99998 99997 99997 99996 99996 99994 99993 99993 99992 99988 99988 99988 99987 99985 99985 99984 99984 99984 99984 99984 99982 99980 99979 99979 99979 99975 99975 99974 99974 99974 99973 99970 99969 99969 99968 99966 99965 99965 99959 99959 99958 99958 99958 99957 99956 99955 99955 99955 99955 99953 99953 99953 99953 99951 99951 99947 99947 99947 99946 99945 99945 99944 99943 99943 99942 99939 99938 99938 99937 99936 99934 99933 99930 99929 99929 99927 99925 99922 99921 99920 99920 99919 99918 99916 99916 99916 99914 99913 99912 99912 99911 99909 99909 99909 99908 99907 99907 .........93 93 92 92 91 90 90 88 87 87 85 85 84 84 83 80 80 79 78 78 76 75 75 74 73 73 72 72 67 67 67 67 66 65 65 65 64 63 62 61 60 59 58 58 57 57 53 52 52 50 49 47 46 45 45 45 45 44 44 42 42 40 39 39 36 35 34 33 33 31 30 29 27 25 24 23 23 23 22 20 19 19 18 16 15 13 13 13 13 13 12 12 12 11 9 8 5 1 1 1
    ---------------
    
    
    快速排序-正序耗时：17 毫秒
    
    1 1 1 5 8 9 11 12 12 12 13 13 13 13 13 15 16 18 19 19 20 22 23 23 23 24 25 27 29 30 31 33 33 34 35 36 39 39 40 42 42 44 44 45 45 45 45 46 47 49 50 52 52 53 57 57 58 58 59 60 61 62 63 64 65 65 65 66 67 67 67 67 72 72 73 73 74 75 75 76 78 78 79 80 80 83 84 84 85 85 87 87 88 90 90 91 92 92 93 93 .........99907 99907 99908 99909 99909 99909 99911 99912 99912 99913 99914 99916 99916 99916 99918 99919 99920 99920 99921 99922 99925 99927 99929 99929 99930 99933 99934 99936 99937 99938 99938 99939 99942 99943 99943 99944 99945 99945 99946 99947 99947 99947 99951 99951 99953 99953 99953 99953 99955 99955 99955 99955 99956 99957 99958 99958 99958 99959 99959 99965 99965 99966 99968 99969 99969 99970 99973 99974 99974 99974 99975 99975 99979 99979 99979 99980 99982 99984 99984 99984 99984 99984 99985 99985 99987 99988 99988 99988 99992 99993 99993 99994 99996 99996 99997 99997 99998 99999 99999 99999
    
    快速排序-倒序耗时：20 毫秒
    
    99999 99999 99999 99998 99997 99997 99996 99996 99994 99993 99993 99992 99988 99988 99988 99987 99985 99985 99984 99984 99984 99984 99984 99982 99980 99979 99979 99979 99975 99975 99974 99974 99974 99973 99970 99969 99969 99968 99966 99965 99965 99959 99959 99958 99958 99958 99957 99956 99955 99955 99955 99955 99953 99953 99953 99953 99951 99951 99947 99947 99947 99946 99945 99945 99944 99943 99943 99942 99939 99938 99938 99937 99936 99934 99933 99930 99929 99929 99927 99925 99922 99921 99920 99920 99919 99918 99916 99916 99916 99914 99913 99912 99912 99911 99909 99909 99909 99908 99907 99907 .........93 93 92 92 91 90 90 88 87 87 85 85 84 84 83 80 80 79 78 78 76 75 75 74 73 73 72 72 67 67 67 67 66 65 65 65 64 63 62 61 60 59 58 58 57 57 53 52 52 50 49 47 46 45 45 45 45 44 44 42 42 40 39 39 36 35 34 33 33 31 30 29 27 25 24 23 23 23 22 20 19 19 18 16 15 13 13 13 13 13 12 12 12 11 9 8 5 1 1 1
    ---------------
    
    
    计数排序-正序耗时：2 毫秒
    
    1 1 1 5 8 9 11 12 12 12 13 13 13 13 13 15 16 18 19 19 20 22 23 23 23 24 25 27 29 30 31 33 33 34 35 36 39 39 40 42 42 44 44 45 45 45 45 46 47 49 50 52 52 53 57 57 58 58 59 60 61 62 63 64 65 65 65 66 67 67 67 67 72 72 73 73 74 75 75 76 78 78 79 80 80 83 84 84 85 85 87 87 88 90 90 91 92 92 93 93 .........99907 99907 99908 99909 99909 99909 99911 99912 99912 99913 99914 99916 99916 99916 99918 99919 99920 99920 99921 99922 99925 99927 99929 99929 99930 99933 99934 99936 99937 99938 99938 99939 99942 99943 99943 99944 99945 99945 99946 99947 99947 99947 99951 99951 99953 99953 99953 99953 99955 99955 99955 99955 99956 99957 99958 99958 99958 99959 99959 99965 99965 99966 99968 99969 99969 99970 99973 99974 99974 99974 99975 99975 99979 99979 99979 99980 99982 99984 99984 99984 99984 99984 99985 99985 99987 99988 99988 99988 99992 99993 99993 99994 99996 99996 99997 99997 99998 99999 99999 99999
    
    计数排序-倒序耗时：1 毫秒
    
    99999 99999 99999 99998 99997 99997 99996 99996 99994 99993 99993 99992 99988 99988 99988 99987 99985 99985 99984 99984 99984 99984 99984 99982 99980 99979 99979 99979 99975 99975 99974 99974 99974 99973 99970 99969 99969 99968 99966 99965 99965 99959 99959 99958 99958 99958 99957 99956 99955 99955 99955 99955 99953 99953 99953 99953 99951 99951 99947 99947 99947 99946 99945 99945 99944 99943 99943 99942 99939 99938 99938 99937 99936 99934 99933 99930 99929 99929 99927 99925 99922 99921 99920 99920 99919 99918 99916 99916 99916 99914 99913 99912 99912 99911 99909 99909 99909 99908 99907 99907 .........93 93 92 92 91 90 90 88 87 87 85 85 84 84 83 80 80 79 78 78 76 75 75 74 73 73 72 72 67 67 67 67 66 65 65 65 64 63 62 61 60 59 58 58 57 57 53 52 52 50 49 47 46 45 45 45 45 44 44 42 42 40 39 39 36 35 34 33 33 31 30 29 27 25 24 23 23 23 22 20 19 19 18 16 15 13 13 13 13 13 12 12 12 11 9 8 5 1 1 1
    请按任意键退出

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29uZTMxMg_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29uZTMxMg_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29uZTMxMg_size_16_color_FFFFFF_t_70 2]

### 12.测试排序100万个无序数 ###

```c
    //主函数
    int main( int argc, char* argv[] ){ 
    	char ch;
    	//测试排序10万个无序数
    	testSort(1000000, true);
    	
    	printf("\r\n请按任意键退出\r\n\r\n");
    	scanf_s("%c", &ch);
    	exit(0);
    }

原始数据：
    895366 917310 945598 295617 404792 235960 936536 188156 255072 882291 165531 978952 419962 403444 137884 585857 385376 399472 954896 199671 460648 880807 38466 959495 66986 278955 866487 158364 287758 52618 834851 465107 610250 464061 213736 412465 265705 799635 920386 928815 181574 808011 219602 397120 114749 870819 985558 693623 176533 788218 310241 971794 880444 62448 445217 748201 354281 682771 276407 875641 798116 267741 219838 837392 78666 371427 74799 737303 218122 266542 262710 932717 60549 743419 802275 522281 370443 24651 73797 369942 219916 752501 556509 862746 904288 587934 363630 797048 522497 427916 232777 82011 307698 535748 772958 749244 345458 928002 364751 622300 .........202514 60000 305108 129882 736190 444612 971603 627570 645989 858977 142475 735341 965065 475677 696039 393322 834930 387513 749456 940138 614260 633061 547127 765777 267490 980125 755124 49374 407622 552436 104181 775015 473954 636458 254394 323230 213523 422111 651784 660852 99776 683494 283732 655010 784132 8210 805731 294123 520739 306548 677863 903434 540679 660420 80142 469293 470022 122496 667922 282996 136440 845616 85425 395650 88324 895195 796490 837473 835265 332475 395927 124861 517184 109469 705524 24520 841872 80555 11676 754219 647734 11375 882988 858700 715530 711865 890122 723135 696202 314219 754739 879737 404927 826243 446707 807374 13582 266524 151552 206351
    ---------------
    
    
    冒泡排序-正序耗时：3109506 毫秒
    
    0 0 0 1 2 3 4 5 6 7 7 7 8 8 8 8 9 11 11 11 13 13 14 15 17 17 17 18 19 21 24 24 24 24 26 27 28 29 30 30 31 32 33 34 34 34 34 35 36 38 39 39 40 42 42 43 44 47 48 50 51 53 55 56 58 58 59 59 59 59 60 61 62 63 63 63 64 64 66 67 69 71 72 73 74 74 74 75 75 77 77 80 80 81 81 82 82 83 84 84 .........999874 999875 999876 999876 999880 999881 999881 999882 999882 999883 999883 999883 999886 999891 999891 999893 999893 999896 999898 999899 999900 999902 999902 999902 999902 999903 999903 999908 999909 999917 999917 999920 999920 999922 999922 999924 999925 999928 999928 999930 999931 999934 999935 999935 999936 999936 999937 999937 999937 999937 999938 999939 999939 999940 999940 999941 999943 999944 999945 999946 999948 999950 999950 999951 999951 999952 999952 999955 999959 999962 999962 999963 999963 999966 999968 999968 999969 999970 999972 999972 999972 999972 999973 999975 999977 999978 999979 999979 999979 999981 999986 999987 999987 999989 999990 999990 999991 999992 999995 999998
    
    冒泡排序-倒序耗时：3077646 毫秒
    
    999998 999995 999992 999991 999990 999990 999989 999987 999987 999986 999981 999979 999979 999979 999978 999977 999975 999973 999972 999972 999972 999972 999970 999969 999968 999968 999966 999963 999963 999962 999962 999959 999955 999952 999952 999951 999951 999950 999950 999948 999946 999945 999944 999943 999941 999940 999940 999939 999939 999938 999937 999937 999937 999937 999936 999936 999935 999935 999934 999931 999930 999928 999928 999925 999924 999922 999922 999920 999920 999917 999917 999909 999908 999903 999903 999902 999902 999902 999902 999900 999899 999898 999896 999893 999893 999891 999891 999886 999883 999883 999883 999882 999882 999881 999881 999880 999876 999876 999875 999874 .........84 84 83 82 82 81 81 80 80 77 77 75 75 74 74 74 73 72 71 69 67 66 64 64 63 63 63 62 61 60 59 59 59 59 58 58 56 55 53 51 50 48 47 44 43 42 42 40 39 39 38 36 35 34 34 34 34 33 32 31 30 30 29 28 27 26 24 24 24 24 21 19 18 17 17 17 15 14 13 13 11 11 11 9 8 8 8 8 7 7 7 6 5 4 3 2 1 0 0 0
    ---------------
    
    
    选择排序-正序耗时：1112611 毫秒
    
    0 0 0 1 2 3 4 5 6 7 7 7 8 8 8 8 9 11 11 11 13 13 14 15 17 17 17 18 19 21 24 24 24 24 26 27 28 29 30 30 31 32 33 34 34 34 34 35 36 38 39 39 40 42 42 43 44 47 48 50 51 53 55 56 58 58 59 59 59 59 60 61 62 63 63 63 64 64 66 67 69 71 72 73 74 74 74 75 75 77 77 80 80 81 81 82 82 83 84 84 .........999874 999875 999876 999876 999880 999881 999881 999882 999882 999883 999883 999883 999886 999891 999891 999893 999893 999896 999898 999899 999900 999902 999902 999902 999902 999903 999903 999908 999909 999917 999917 999920 999920 999922 999922 999924 999925 999928 999928 999930 999931 999934 999935 999935 999936 999936 999937 999937 999937 999937 999938 999939 999939 999940 999940 999941 999943 999944 999945 999946 999948 999950 999950 999951 999951 999952 999952 999955 999959 999962 999962 999963 999963 999966 999968 999968 999969 999970 999972 999972 999972 999972 999973 999975 999977 999978 999979 999979 999979 999981 999986 999987 999987 999989 999990 999990 999991 999992 999995 999998
    
    选择排序-倒序耗时：1103137 毫秒
    
    999998 999995 999992 999991 999990 999990 999989 999987 999987 999986 999981 999979 999979 999979 999978 999977 999975 999973 999972 999972 999972 999972 999970 999969 999968 999968 999966 999963 999963 999962 999962 999959 999955 999952 999952 999951 999951 999950 999950 999948 999946 999945 999944 999943 999941 999940 999940 999939 999939 999938 999937 999937 999937 999937 999936 999936 999935 999935 999934 999931 999930 999928 999928 999925 999924 999922 999922 999920 999920 999917 999917 999909 999908 999903 999903 999902 999902 999902 999902 999900 999899 999898 999896 999893 999893 999891 999891 999886 999883 999883 999883 999882 999882 999881 999881 999880 999876 999876 999875 999874 .........84 84 83 82 82 81 81 80 80 77 77 75 75 74 74 74 73 72 71 69 67 66 64 64 63 63 63 62 61 60 59 59 59 59 58 58 56 55 53 51 50 48 47 44 43 42 42 40 39 39 38 36 35 34 34 34 34 33 32 31 30 30 29 28 27 26 24 24 24 24 21 19 18 17 17 17 15 14 13 13 11 11 11 9 8 8 8 8 7 7 7 6 5 4 3 2 1 0 0 0
    ---------------
    
    
    插入排序-正序耗时：654884 毫秒
    
    0 0 0 1 2 3 4 5 6 7 7 7 8 8 8 8 9 11 11 11 13 13 14 15 17 17 17 18 19 21 24 24 24 24 26 27 28 29 30 30 31 32 33 34 34 34 34 35 36 38 39 39 40 42 42 43 44 47 48 50 51 53 55 56 58 58 59 59 59 59 60 61 62 63 63 63 64 64 66 67 69 71 72 73 74 74 74 75 75 77 77 80 80 81 81 82 82 83 84 84 .........999874 999875 999876 999876 999880 999881 999881 999882 999882 999883 999883 999883 999886 999891 999891 999893 999893 999896 999898 999899 999900 999902 999902 999902 999902 999903 999903 999908 999909 999917 999917 999920 999920 999922 999922 999924 999925 999928 999928 999930 999931 999934 999935 999935 999936 999936 999937 999937 999937 999937 999938 999939 999939 999940 999940 999941 999943 999944 999945 999946 999948 999950 999950 999951 999951 999952 999952 999955 999959 999962 999962 999963 999963 999966 999968 999968 999969 999970 999972 999972 999972 999972 999973 999975 999977 999978 999979 999979 999979 999981 999986 999987 999987 999989 999990 999990 999991 999992 999995 999998
    
    插入排序-倒序耗时：649668 毫秒
    
    999998 999995 999992 999991 999990 999990 999989 999987 999987 999986 999981 999979 999979 999979 999978 999977 999975 999973 999972 999972 999972 999972 999970 999969 999968 999968 999966 999963 999963 999962 999962 999959 999955 999952 999952 999951 999951 999950 999950 999948 999946 999945 999944 999943 999941 999940 999940 999939 999939 999938 999937 999937 999937 999937 999936 999936 999935 999935 999934 999931 999930 999928 999928 999925 999924 999922 999922 999920 999920 999917 999917 999909 999908 999903 999903 999902 999902 999902 999902 999900 999899 999898 999896 999893 999893 999891 999891 999886 999883 999883 999883 999882 999882 999881 999881 999880 999876 999876 999875 999874 .........84 84 83 82 82 81 81 80 80 77 77 75 75 74 74 74 73 72 71 69 67 66 64 64 63 63 63 62 61 60 59 59 59 59 58 58 56 55 53 51 50 48 47 44 43 42 42 40 39 39 38 36 35 34 34 34 34 33 32 31 30 30 29 28 27 26 24 24 24 24 21 19 18 17 17 17 15 14 13 13 11 11 11 9 8 8 8 8 7 7 7 6 5 4 3 2 1 0 0 0
    ---------------
    
    
    归并排序-正序耗时：649818 毫秒
    
    0 0 0 1 2 3 4 5 6 7 7 7 8 8 8 8 9 11 11 11 13 13 14 15 17 17 17 18 19 21 24 24 24 24 26 27 28 29 30 30 31 32 33 34 34 34 34 35 36 38 39 39 40 42 42 43 44 47 48 50 51 53 55 56 58 58 59 59 59 59 60 61 62 63 63 63 64 64 66 67 69 71 72 73 74 74 74 75 75 77 77 80 80 81 81 82 82 83 84 84 .........999874 999875 999876 999876 999880 999881 999881 999882 999882 999883 999883 999883 999886 999891 999891 999893 999893 999896 999898 999899 999900 999902 999902 999902 999902 999903 999903 999908 999909 999917 999917 999920 999920 999922 999922 999924 999925 999928 999928 999930 999931 999934 999935 999935 999936 999936 999937 999937 999937 999937 999938 999939 999939 999940 999940 999941 999943 999944 999945 999946 999948 999950 999950 999951 999951 999952 999952 999955 999959 999962 999962 999963 999963 999966 999968 999968 999969 999970 999972 999972 999972 999972 999973 999975 999977 999978 999979 999979 999979 999981 999986 999987 999987 999989 999990 999990 999991 999992 999995 999998
    
    归并排序-倒序耗时：654581 毫秒
    
    999998 999995 999992 999991 999990 999990 999989 999987 999987 999986 999981 999979 999979 999979 999978 999977 999975 999973 999972 999972 999972 999972 999970 999969 999968 999968 999966 999963 999963 999962 999962 999959 999955 999952 999952 999951 999951 999950 999950 999948 999946 999945 999944 999943 999941 999940 999940 999939 999939 999938 999937 999937 999937 999937 999936 999936 999935 999935 999934 999931 999930 999928 999928 999925 999924 999922 999922 999920 999920 999917 999917 999909 999908 999903 999903 999902 999902 999902 999902 999900 999899 999898 999896 999893 999893 999891 999891 999886 999883 999883 999883 999882 999882 999881 999881 999880 999876 999876 999875 999874 .........84 84 83 82 82 81 81 80 80 77 77 75 75 74 74 74 73 72 71 69 67 66 64 64 63 63 63 62 61 60 59 59 59 59 58 58 56 55 53 51 50 48 47 44 43 42 42 40 39 39 38 36 35 34 34 34 34 33 32 31 30 30 29 28 27 26 24 24 24 24 21 19 18 17 17 17 15 14 13 13 11 11 11 9 8 8 8 8 7 7 7 6 5 4 3 2 1 0 0 0
    ---------------
    
    
    堆排序-正序耗时：684 毫秒
    
    0 0 0 1 2 3 4 5 6 7 7 7 8 8 8 8 9 11 11 11 13 13 14 15 17 17 17 18 19 21 24 24 24 24 26 27 28 29 30 30 31 32 33 34 34 34 34 35 36 38 39 39 40 42 42 43 44 47 48 50 51 53 55 56 58 58 59 59 59 59 60 61 62 63 63 63 64 64 66 67 69 71 72 73 74 74 74 75 75 77 77 80 80 81 81 82 82 83 84 84 .........999874 999875 999876 999876 999880 999881 999881 999882 999882 999883 999883 999883 999886 999891 999891 999893 999893 999896 999898 999899 999900 999902 999902 999902 999902 999903 999903 999908 999909 999917 999917 999920 999920 999922 999922 999924 999925 999928 999928 999930 999931 999934 999935 999935 999936 999936 999937 999937 999937 999937 999938 999939 999939 999940 999940 999941 999943 999944 999945 999946 999948 999950 999950 999951 999951 999952 999952 999955 999959 999962 999962 999963 999963 999966 999968 999968 999969 999970 999972 999972 999972 999972 999973 999975 999977 999978 999979 999979 999979 999981 999986 999987 999987 999989 999990 999990 999991 999992 999995 999998
    
    堆排序-倒序耗时：734 毫秒
    
    999998 999995 999992 999991 999990 999990 999989 999987 999987 999986 999981 999979 999979 999979 999978 999977 999975 999973 999972 999972 999972 999972 999970 999969 999968 999968 999966 999963 999963 999962 999962 999959 999955 999952 999952 999951 999951 999950 999950 999948 999946 999945 999944 999943 999941 999940 999940 999939 999939 999938 999937 999937 999937 999937 999936 999936 999935 999935 999934 999931 999930 999928 999928 999925 999924 999922 999922 999920 999920 999917 999917 999909 999908 999903 999903 999902 999902 999902 999902 999900 999899 999898 999896 999893 999893 999891 999891 999886 999883 999883 999883 999882 999882 999881 999881 999880 999876 999876 999875 999874 .........84 84 83 82 82 81 81 80 80 77 77 75 75 74 74 74 73 72 71 69 67 66 64 64 63 63 63 62 61 60 59 59 59 59 58 58 56 55 53 51 50 48 47 44 43 42 42 40 39 39 38 36 35 34 34 34 34 33 32 31 30 30 29 28 27 26 24 24 24 24 21 19 18 17 17 17 15 14 13 13 11 11 11 9 8 8 8 8 7 7 7 6 5 4 3 2 1 0 0 0
    ---------------
    
    
    希尔排序-正序耗时：335 毫秒
    
    0 0 0 1 2 3 4 5 6 7 7 7 8 8 8 8 9 11 11 11 13 13 14 15 17 17 17 18 19 21 24 24 24 24 26 27 28 29 30 30 31 32 33 34 34 34 34 35 36 38 39 39 40 42 42 43 44 47 48 50 51 53 55 56 58 58 59 59 59 59 60 61 62 63 63 63 64 64 66 67 69 71 72 73 74 74 74 75 75 77 77 80 80 81 81 82 82 83 84 84 .........999874 999875 999876 999876 999880 999881 999881 999882 999882 999883 999883 999883 999886 999891 999891 999893 999893 999896 999898 999899 999900 999902 999902 999902 999902 999903 999903 999908 999909 999917 999917 999920 999920 999922 999922 999924 999925 999928 999928 999930 999931 999934 999935 999935 999936 999936 999937 999937 999937 999937 999938 999939 999939 999940 999940 999941 999943 999944 999945 999946 999948 999950 999950 999951 999951 999952 999952 999955 999959 999962 999962 999963 999963 999966 999968 999968 999969 999970 999972 999972 999972 999972 999973 999975 999977 999978 999979 999979 999979 999981 999986 999987 999987 999989 999990 999990 999991 999992 999995 999998
    
    希尔排序-倒序耗时：328 毫秒
    
    999998 999995 999992 999991 999990 999990 999989 999987 999987 999986 999981 999979 999979 999979 999978 999977 999975 999973 999972 999972 999972 999972 999970 999969 999968 999968 999966 999963 999963 999962 999962 999959 999955 999952 999952 999951 999951 999950 999950 999948 999946 999945 999944 999943 999941 999940 999940 999939 999939 999938 999937 999937 999937 999937 999936 999936 999935 999935 999934 999931 999930 999928 999928 999925 999924 999922 999922 999920 999920 999917 999917 999909 999908 999903 999903 999902 999902 999902 999902 999900 999899 999898 999896 999893 999893 999891 999891 999886 999883 999883 999883 999882 999882 999881 999881 999880 999876 999876 999875 999874 .........84 84 83 82 82 81 81 80 80 77 77 75 75 74 74 74 73 72 71 69 67 66 64 64 63 63 63 62 61 60 59 59 59 59 58 58 56 55 53 51 50 48 47 44 43 42 42 40 39 39 38 36 35 34 34 34 34 33 32 31 30 30 29 28 27 26 24 24 24 24 21 19 18 17 17 17 15 14 13 13 11 11 11 9 8 8 8 8 7 7 7 6 5 4 3 2 1 0 0 0
    ---------------
    
    
    快速排序-正序耗时：169 毫秒
    
    0 0 0 1 2 3 4 5 6 7 7 7 8 8 8 8 9 11 11 11 13 13 14 15 17 17 17 18 19 21 24 24 24 24 26 27 28 29 30 30 31 32 33 34 34 34 34 35 36 38 39 39 40 42 42 43 44 47 48 50 51 53 55 56 58 58 59 59 59 59 60 61 62 63 63 63 64 64 66 67 69 71 72 73 74 74 74 75 75 77 77 80 80 81 81 82 82 83 84 84 .........999874 999875 999876 999876 999880 999881 999881 999882 999882 999883 999883 999883 999886 999891 999891 999893 999893 999896 999898 999899 999900 999902 999902 999902 999902 999903 999903 999908 999909 999917 999917 999920 999920 999922 999922 999924 999925 999928 999928 999930 999931 999934 999935 999935 999936 999936 999937 999937 999937 999937 999938 999939 999939 999940 999940 999941 999943 999944 999945 999946 999948 999950 999950 999951 999951 999952 999952 999955 999959 999962 999962 999963 999963 999966 999968 999968 999969 999970 999972 999972 999972 999972 999973 999975 999977 999978 999979 999979 999979 999981 999986 999987 999987 999989 999990 999990 999991 999992 999995 999998
    
    快速排序-倒序耗时：179 毫秒
    
    999998 999995 999992 999991 999990 999990 999989 999987 999987 999986 999981 999979 999979 999979 999978 999977 999975 999973 999972 999972 999972 999972 999970 999969 999968 999968 999966 999963 999963 999962 999962 999959 999955 999952 999952 999951 999951 999950 999950 999948 999946 999945 999944 999943 999941 999940 999940 999939 999939 999938 999937 999937 999937 999937 999936 999936 999935 999935 999934 999931 999930 999928 999928 999925 999924 999922 999922 999920 999920 999917 999917 999909 999908 999903 999903 999902 999902 999902 999902 999900 999899 999898 999896 999893 999893 999891 999891 999886 999883 999883 999883 999882 999882 999881 999881 999880 999876 999876 999875 999874 .........84 84 83 82 82 81 81 80 80 77 77 75 75 74 74 74 73 72 71 69 67 66 64 64 63 63 63 62 61 60 59 59 59 59 58 58 56 55 53 51 50 48 47 44 43 42 42 40 39 39 38 36 35 34 34 34 34 33 32 31 30 30 29 28 27 26 24 24 24 24 21 19 18 17 17 17 15 14 13 13 11 11 11 9 8 8 8 8 7 7 7 6 5 4 3 2 1 0 0 0
    ---------------
    
    
    计数排序-正序耗时：19 毫秒
    
    0 0 0 1 2 3 4 5 6 7 7 7 8 8 8 8 9 11 11 11 13 13 14 15 17 17 17 18 19 21 24 24 24 24 26 27 28 29 30 30 31 32 33 34 34 34 34 35 36 38 39 39 40 42 42 43 44 47 48 50 51 53 55 56 58 58 59 59 59 59 60 61 62 63 63 63 64 64 66 67 69 71 72 73 74 74 74 75 75 77 77 80 80 81 81 82 82 83 84 84 .........999874 999875 999876 999876 999880 999881 999881 999882 999882 999883 999883 999883 999886 999891 999891 999893 999893 999896 999898 999899 999900 999902 999902 999902 999902 999903 999903 999908 999909 999917 999917 999920 999920 999922 999922 999924 999925 999928 999928 999930 999931 999934 999935 999935 999936 999936 999937 999937 999937 999937 999938 999939 999939 999940 999940 999941 999943 999944 999945 999946 999948 999950 999950 999951 999951 999952 999952 999955 999959 999962 999962 999963 999963 999966 999968 999968 999969 999970 999972 999972 999972 999972 999973 999975 999977 999978 999979 999979 999979 999981 999986 999987 999987 999989 999990 999990 999991 999992 999995 999998
    
    计数排序-倒序耗时：19 毫秒
    
    999998 999995 999992 999991 999990 999990 999989 999987 999987 999986 999981 999979 999979 999979 999978 999977 999975 999973 999972 999972 999972 999972 999970 999969 999968 999968 999966 999963 999963 999962 999962 999959 999955 999952 999952 999951 999951 999950 999950 999948 999946 999945 999944 999943 999941 999940 999940 999939 999939 999938 999937 999937 999937 999937 999936 999936 999935 999935 999934 999931 999930 999928 999928 999925 999924 999922 999922 999920 999920 999917 999917 999909 999908 999903 999903 999902 999902 999902 999902 999900 999899 999898 999896 999893 999893 999891 999891 999886 999883 999883 999883 999882 999882 999881 999881 999880 999876 999876 999875 999874 .........84 84 83 82 82 81 81 80 80 77 77 75 75 74 74 74 73 72 71 69 67 66 64 64 63 63 63 62 61 60 59 59 59 59 58 58 56 55 53 51 50 48 47 44 43 42 42 40 39 39 38 36 35 34 34 34 34 33 32 31 30 30 29 28 27 26 24 24 24 24 21 19 18 17 17 17 15 14 13 13 11 11 11 9 8 8 8 8 7 7 7 6 5 4 3 2 1 0 0 0
    请按任意键退出

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29uZTMxMg_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29uZTMxMg_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29uZTMxMg_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29uZTMxMg_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29uZTMxMg_size_16_color_FFFFFF_t_70 7]

### 13.主函数和测试排序相关函数 ###

//主函数
    //author：Hengda
    int main(int argc, char* argv[]) { 
    	char ch;
    	
    	testSort(100000, true);//测试10万个数
    	
    	printf("\r\n请按任意键退出\r\n\r\n");
    	scanf_s("%c", &ch);
    	exit(0);
    }
    
    //测试排序
    //author：Hengda
    //total：想要测试排序的元素数
    //isPrintArrData：true 打印，false不打印
    int testSort(int total, bool isPrintArrData) { 
    
    	int* arr, i, m = 0, n = total - 1;
    	//随机生成total个无序数
    	if ((arr = makeData(total, m, n)) != NULL) { 
    	
    		//打印原始数据
    		printf("原始数据：\r\n");
    		printArrData(arr, total);
    		
    		//以下为调用各排序算法函数，对上面生成的total个无序数分别进行正序倒序排序
    		printf("\r\n---------------\r\n");
    		testOneSortFunc((char*)"bubbleSort", (char*)"冒泡排序", arr, total, false, isPrintArrData);
    		testOneSortFunc((char*)"bubbleSort", (char*)"冒泡排序", arr, total, true, isPrintArrData);
    		printf("\r\n---------------\r\n");
    		testOneSortFunc((char*)"selectionSort", (char*)"选择排序", arr, total, false, isPrintArrData);
    		testOneSortFunc((char*)"selectionSort", (char*)"选择排序", arr, total, true, isPrintArrData);
    		printf("\r\n---------------\r\n");
    		testOneSortFunc((char*)"insertionSort", (char*)"插入排序", arr, total, false, isPrintArrData);
    		testOneSortFunc((char*)"insertionSort", (char*)"插入排序", arr, total, true, isPrintArrData);
    		printf("\r\n---------------\r\n");
    		testOneSortFunc((char*)"mergeSort", (char*)"归并排序", arr, total, false, isPrintArrData);
    		testOneSortFunc((char*)"mergeSort", (char*)"归并排序", arr, total, true, isPrintArrData);
    		printf("\r\n---------------\r\n");
    		testOneSortFunc((char*)"heapSort", (char*)"堆排序", arr, total, false, isPrintArrData);
    		testOneSortFunc((char*)"heapSort", (char*)"堆排序", arr, total, true, isPrintArrData);
    		printf("\r\n---------------\r\n");
    		testOneSortFunc((char*)"shellSort", (char*)"希尔排序", arr, total, false, isPrintArrData);
    		testOneSortFunc((char*)"shellSort", (char*)"希尔排序", arr, total, true, isPrintArrData);
    		printf("\r\n---------------\r\n");
    		testOneSortFunc((char*)"quickSort", (char*)"快速排序", arr, total, false, isPrintArrData);
    		testOneSortFunc((char*)"quickSort", (char*)"快速排序", arr, total, true, isPrintArrData);
    		printf("\r\n---------------\r\n");
    		testOneSortFunc((char*)"countingSort", (char*)"计数排序", arr, total, false, isPrintArrData);
    		testOneSortFunc((char*)"countingSort", (char*)"计数排序", arr, total, true, isPrintArrData);
    
    		//释放由malloc申请的内存
    		free(arr);
    		arr = NULL;
    		return 0;
    	}
    	else { 
    		//释放由malloc申请的内存
    		free(arr);
    		arr = NULL;
    		return -1;
    	}
    }
    
    //测试一个排序函数
    //author：Hengda
    //funcName：被调用函数名称
    //textName：函数标题或描述
    //arr：待排序数据数组
    //len：待排序数据长度
    //mode：true倒序，false正序
    //isPrintArrData：true 打印排序结果数据，false 不打印
    int testOneSortFunc(char* funName, char* textName, int* arr, int len, bool mode, bool isPrintArrData) { 
    	long stime, etime;//用于记录排序前后的时间时间戳
    	int memsize = len * sizeof(int);//需要申请的内存空间大小（和arr的内存一样大）
    	int* arr1 = (int*)malloc(memsize);//申请内存空间
    	//复制数组数据到新申请的内存空间，避免排序后改变原数组的结果
    	memcpy(arr1, arr, memsize);
    	
    	//记录排序前时间戳
    	stime = getTimeStamp();
    	//开始调用排序函数
    	if (strcmp(funName, "bubbleSort") == 0) bubbleSort(arr1, len, mode);
    	else if (strcmp(funName, "selectionSort") == 0) selectionSort(arr1, len, mode);
    	else if (strcmp(funName, "insertionSort") == 0) insertionSort(arr1, len, mode);
    	else if (strcmp(funName, "quickSort") == 0) quickSort(arr1, 0, len - 1, mode);
    	else if (strcmp(funName, "shellSort") == 0) shellSort(arr1, len, mode);
    	else if (strcmp(funName, "heapSort") == 0) heapSort(arr1, len, mode);
    	else if (strcmp(funName, "countingSort") == 0) countingSort(arr1, len, mode);
    	else if (strcmp(funName, "mergeSort") == 0) mergeSort(arr1, 0, len - 1, mode);
    	else return 0;
    	//记录排序后时间戳
    	etime = getTimeStamp();
    	printf("\r\n\r\n%s-%s序耗时：%ld 毫秒 \r\n\r\n", textName, mode ? "倒" : "正", etime - stime);
    	//打印排序结果
    	if (isPrintArrData) printArrData(arr1, len);
    	//释放动态申请的内存空间
    	free(arr1);
    	arr1 = NULL;
    
    	return 0;
    }
    
    //打印数组内容
    //author：Hengda
    //arr 待打印数组
    //len 数组元素数
    void printArrData(int* arr, int len) { 
    	int i, startPrint;
    	for (i = 0; i < ((len > 100) ? 100 : len); i++) { 
    		//for (i = 0; i < total; i++) { 
    		printf("%d ", arr[i]);
    	}
    	startPrint = (((len - 100) > 100) ? len - 100 : 100);
    	if (len > 100) { 
    		printf(".........");
    		for (i = startPrint; i < len; i++) { 
    			//for (i = 0; i < total; i++) { 
    			printf("%d ", arr[i]);
    		}
    	}
    }
    //生成随机数数组
    //author：Hengda
    //total 需要生成的元素数量
    //m,n 指定需要生成元素值的范围（含 m和n）
    int* makeData(int total, int m, int n){ 
    	int i;
    	int* arr = (int*)malloc(sizeof(int) * total);//申请存储total个数需要的内存空间
    	if (arr == NULL) { 
    		printf("申请动态内存失败！\r\n");
    		return NULL;
    	}
    
    	srand(time(0));
    	//逐个生成，共生成total个元素
    	for (i = 0; i < total; i++) { 
    		arr[i] = getRandNum( m, n );
    	}
    	return arr;
    }
    
    //获取一个m-n之间的随机数（包括m和n）
    //author：Hengda
    //m,n 指定需要生成元素值的范围（含 m和n）
    //本策略是，诸位随机生成(0-9的数)，最终拼凑成0至n-m间的数，然后再加上m，即满足介于m和n间的随机数
    int getRandNum( int m, int n ) { 
    	int range = n - m + 1;
    	int range1 = range;
    	int reminder = range % 10;
    	int num = 0;
    	//srand(time(0));
    	//每一位都随机生成
    	range = range / 10;
    	while (range / 10 > 0 ) { 
    		num += rand() % 10;
    		num *= 10;
    		range = range / 10;
    	}
    	num += rand() % ( range1 >=10 ? 10 : (reminder + 1) );
    	return num + m;
    }
    //读取当前毫秒时间戳
    //author：Hengda
    long long getTimeStamp(){ 
    	timeb tm;
    	ftime(&tm);
    	return tm.time * 1000 + tm.millitm;
    }

参考知识点：  
1.[C语言随机数的生成【详解】][C]  
2.[VC使用scanf 会报错：VS 编译错误【error C4996: ‘scanf’: This function or variable may be unsafe. 】的解决方案][VC_scanf _VS _error C4996_ _scanf_ This function or variable may be unsafe.]  
3.[c语言中不用scanf要用什么来代替（大一初学者，求浅解）？][c_scanf]  
4.[为什么JavaScript看起来比C ++快4倍？(Why does JavaScript appear to be 4 times faster than C++ ? )][JavaScript_C _4_Why does JavaScript appear to be 4 times faster than C_ _]  
5.[VC/c++版本获取现行时间戳精确到毫秒][VC_c]  
6.[消除VS中动态申请二维数组C6011，C6385，C6386的警告][VS_C6011_C6385_C6386]

其他知识点：  
1.[C++中各种数据类型占据字节长度][C 1]  
2.[VS中更改栈和堆空间的大小][VS]  
3.[vs2010设置堆栈大小][vs2010]  
4.[VS中更改栈和堆空间的大小][VS 1]  
5.[修改visual studio的默认堆栈大小][visual studio]  
6.[C语言 全局变量和局部变量的大小限制][C_]  
7.[如何更改Visual Studio 2019的语言][Visual Studio 2019]  
8.[通过函数名字符串调用函数【C语言版】][C 2]  
9.[在32位系统中，int类型的最大值是多少？][32_int]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29uZTMxMg_size_16_color_FFFFFF_t_70]: /images/20221024/ba57f8193b364487915d6a1b1e6ccd82.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29uZTMxMg_size_16_color_FFFFFF_t_70 1]: /images/20221024/f986b4913822427db20bd6aacf98a393.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29uZTMxMg_size_16_color_FFFFFF_t_70 2]: /images/20221024/f254c926422349e989a2b00fe7fa1118.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29uZTMxMg_size_16_color_FFFFFF_t_70 3]: /images/20221024/eefb53de129d46a58e351588a08bfbe0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29uZTMxMg_size_16_color_FFFFFF_t_70 4]: /images/20221024/173bba1707ca4f3db45511be4ecc93c0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29uZTMxMg_size_16_color_FFFFFF_t_70 5]: /images/20221024/3885c5a1fab940a1aac2d1817ad9b74b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29uZTMxMg_size_16_color_FFFFFF_t_70 6]: /images/20221024/9d8bed525f1741dca8e31be0186d1b1a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29uZTMxMg_size_16_color_FFFFFF_t_70 7]: /images/20221024/afc7cb65c6304015a0af3413986cfabb.png
[C]: https://blog.csdn.net/weixin_46022083/article/details/106661495%29https://blog.csdn.net/weixin_46022083/article/details/106661495
[VC_scanf _VS _error C4996_ _scanf_ This function or variable may be unsafe.]: https://www.cnblogs.com/ZY-Dream/p/10695601.html
[c_scanf]: https://zhidao.baidu.com/question/162240604.html
[JavaScript_C _4_Why does JavaScript appear to be 4 times faster than C_ _]: https://www.it1352.com/1968837.html
[VC_c]: http://blog.chinaunix.net/uid-20637781-id-5831211.html
[VS_C6011_C6385_C6386]: https://www.cnblogs.com/wowpH/p/vs_6011_6385_6386.html
[C 1]: https://www.cnblogs.com/huyihao/p/5984610.html
[VS]: https://www.cnblogs.com/sosi/archive/2011/03/27/1997180.html
[vs2010]: https://www.cnblogs.com/xlw1219/archive/2013/03/15/2961352.html
[VS 1]: https://blog.csdn.net/ALLENJIAO/article/details/8516049
[visual studio]: https://www.meiwen.com.cn/subject/rfbsictx.html
[C_]: http://www.slyar.com/blog/variable-overflow-static.html
[Visual Studio 2019]: https://blog.csdn.net/hedon954/article/details/104736138
[C 2]: https://blog.csdn.net/oscar999/article/details/8986088
[32_int]: http://www.voidcn.com/article/p-afdfnbyc-nw.html