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);}

排序結果

---------------氣泡排序-正序耗時：43491 毫秒氣泡排序-倒序耗時：43409 毫秒---------------選擇排序-正序耗時：15733 毫秒選擇排序-倒序耗時：15330 毫秒--------------插入排序-正序耗時：12006 毫秒插入排序-倒序耗時：8730 毫秒---------------歸併排序-正序耗時：8837 毫秒歸併排序-倒序耗時：8610 毫秒--------------堆排序-正序耗時：58 毫秒堆排序-倒序耗時：50 毫秒---------------希爾排序-正序耗時：45 毫秒希爾排序-倒序耗時：25 毫秒--------------快速排序-正序耗時：17 毫秒快速排序-倒序耗時：20 毫秒--------------計數排序-正序耗時：2 毫秒計數排序-倒序耗時：1 毫秒請按任意鍵退出

12.測試排序100萬個無序數

//主函式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);}

測試結果

---------------氣泡排序-正序耗時：3109506 毫秒氣泡排序-倒序耗時：3077646 毫秒---------------選擇排序-正序耗時：1112611 毫秒選擇排序-倒序耗時：1103137 毫秒---------------插入排序-正序耗時：654884 毫秒插入排序-倒序耗時：649668 毫秒---------------歸併排序-正序耗時：649818 毫秒歸併排序-倒序耗時：654581 毫秒--------------堆排序-正序耗時：684 毫秒堆排序-倒序耗時：734 毫秒---------------希爾排序-正序耗時：335 毫秒希爾排序-倒序耗時：328 毫秒---------------快速排序-正序耗時：169 毫秒快速排序-倒序耗時：179 毫秒---------------計數排序-正序耗時：19 毫秒計數排序-倒序耗時：19 毫秒請按任意鍵退出

13.主函式和測試排序相關函式

//主函式//author：Hengdaint 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：Hengdalong long getTimeStamp(){	timeb tm;	ftime(&tm);	return tm.time * 1000 + tm.millitm;}