程序员求职经验分享与学习资料整理平台

网站首页 > 文章精选 正文

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

balukai 2025-02-08 10:00:04 文章精选 4 ℃

1.引入所需文件

#include 
#include  #动态申请内存
#include 
#include 
#include 
#include

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

Tags：

猜你喜欢

最近发表
标签列表