快捷導航

C語言遞歸實現(xiàn)歸并排序詳解

更新時間：2022年03月01日 15:31:07 作者：Icy?Hunter

這篇文章主要為大家詳細介紹了C語言遞歸實現(xiàn)歸并排序，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，?希望能夠給你帶來幫助

歸并排序遞歸實現(xiàn)還是比較難理解的，感覺涉及遞歸一般理解起來都會比較有難度吧，但是看了b站視頻，然后照著打下來，然后自己寫了點注釋，就發(fā)現(xiàn)不知不覺都大概懂了。

這里的歸并講的是升序排序

歸并排序思路大概就是：先劃分數(shù)組，將數(shù)組劃分為左右半?yún)^(qū)，分成的左右半?yún)^(qū)，各自再劃分左右半?yún)^(qū)，一直劃分，直到最后左右半?yún)^(qū)的元素都為一個時，開始合并，因為都劃分為一個元素了，那么此時兩個元素的排序就非常簡單了，只需要比較大小就可以排序了，那么回溯上去會發(fā)現(xiàn)每組都是兩兩有序了，那么直接再依次比較兩組之間的排頭元素即可，取較小的賦值給臨時數(shù)組，然后排頭元素就變成后一個元素，一直這么比較，直到兩組數(shù)據(jù)有一組為空時，只需要將另一組不為空的接在臨時數(shù)組后面即可，因為此時不為空的剩下的元素是有序的且都比此時有序的臨時數(shù)組大，接完之后臨時數(shù)組就變成有序的數(shù)組了，那么再將臨時數(shù)組的元素復制到實際數(shù)組中去，最后釋放臨時數(shù)組空間，輸出實際數(shù)組，歸并排序結(jié)束，輸出的元素也是排好序的元素了。

這樣干講一定很抽象

這是b站視頻里的圖，十分生動形象了吧。

在這里插入圖片描述

代碼如下（除了視頻里的注釋，還加了點自己的注釋）

#include<bits/stdc++.h>
using namespace std;
void print_arr(int arr[], int n){
	for(int i=0; i<n; i++){
		printf("%d ", arr[i]);
	}
	printf("\n"); 
}
//合并 
void merge(int arr[], int tempArr[], int left, int mid, int right){
	//標記左半?yún)^(qū)第一個未排序元素
	int l_pos = left; 
	//標記右半?yún)^(qū)第一個未排序元素 
	int r_pos = mid+1;
	//合并數(shù)組由左右半?yún)^(qū)構(gòu)成，臨時數(shù)組的開始位置也就是左半?yún)^(qū)的開始位置 
	int pos = left;
	//合并
	//劃分剛結(jié)束后左右半?yún)^(qū)其實各自只有一個元素，那么直接比較大小即為兩個元素的排序。 
	while(l_pos <= mid && r_pos <= right){//當左右半?yún)^(qū)都含有元素時 
		if(arr[l_pos] < arr[r_pos]) //左半?yún)^(qū)第一個剩余元素更小 
		     tempArr[pos++] = arr[l_pos++];//賦值后pos+1，l_pos+1為下一次做準備 
	    else //右半?yún)^(qū)第一個剩余元素更小 
		     tempArr[pos++] = arr[r_pos++];
	}
	//當右半?yún)^(qū)元素合并完后左半?yún)^(qū)還有元素剩余，此時右半?yún)^(qū)有序且都比左半?yún)^(qū)元素大
	//那么直接將剩余的右半?yún)^(qū)元素接上即可 
	//合并左半?yún)^(qū)剩余的元素
	while(l_pos <= mid)tempArr[pos++] = arr[l_pos++]; 
	//同理 
	//合并右半?yún)^(qū)剩余的元素
	while(r_pos <= right)tempArr[pos++] = arr[r_pos++];
	//把臨時數(shù)組中合并后的元素復制回原來的數(shù)組
	//tempArr此時已有序，只需利用left,right即排完序后的左右半?yún)^(qū)復制回arr數(shù)組即可 
	while(left <= right){
		arr[left] = tempArr[left];
		left++;
	}
}
//歸并排序 
void msort(int arr[], int tempArr[], int left, int right){
	//如果只有一個元素，那么就不需要繼續(xù)劃分
	//由 mid = (left + right) / 2得，當只剩最后一個數(shù)時 mid會和left和right相等
	//即傳入后的left和right會相等 
	if(left < right){  //left和right不相等，不止一個元素，需要繼續(xù)劃分 
		//找中間點 
		int mid = (left + right) / 2;
		//遞歸劃分左半?yún)^(qū) 
		msort(arr, tempArr, left, mid);
		//遞歸劃分右半?yún)^(qū) 
		msort(arr, tempArr, mid+1, right); 
		//當數(shù)組劃分完畢時開始進行合并 
		//合并已經(jīng)排序的部分 
		//left為左半?yún)^(qū)左邊界
		//right為右半?yún)^(qū)右邊界
		//mid為劃分左右半?yún)^(qū)的分界（也是左半?yún)^(qū)的右邊界） 
		merge(arr, tempArr, left, mid, right);
	} 
}
//歸并入口 
void merge_sort(int arr[], int n){
	//分配一個輔助的數(shù)組，內(nèi)存大小為 數(shù)組數(shù)*數(shù)據(jù)類型占位 
	int* tempArr = (int*)malloc(n * sizeof(int));
	 if(tempArr){
	 	//tempArr為臨時數(shù)組, arr為需要排序的數(shù)組
		//排序下標為0至n-1，n為數(shù)組大小 
	 	msort(arr, tempArr, 0, n-1);
	 	free(tempArr);//釋放內(nèi)存空間 
	 }
	 else{
	 	printf("meet error");
	 }
}
int main(){
	int arr[] = {9, 5, 2, 7, 12, 4, 3, 1, 11};
	int n = 9;
	//打印原來的數(shù)組 
	print_arr(arr, n);
	//歸并排序 
	merge_sort(arr, n);
	//打印排完序的數(shù)組 
	print_arr(arr, n);
	return 0;
}