歸并排序

hlcc 發(fā)布于2021-10-08 10:05 / 1248人閱讀

摘要：代碼解析自見文中慢慢理解細(xì)細(xì)入深開辟分配一個(gè)輔助臨時(shí)數(shù)組開辟成功之后實(shí)現(xiàn)歸并之前的劃分?jǐn)?shù)組步驟利用之后立刻釋放空間開辟失敗每一次找中間值依次劃分遞歸劃分后左邊的新一塊遞歸劃分后右邊的一塊合并已劃分排序好的數(shù)組一直為標(biāo)記左半?yún)^(qū)第一個(gè)未排序

代碼解析自見文中

慢慢理解細(xì)細(xì)入深

#include#includevoid Print(int arr[], int sz){	int i = 0;	for (i = 0; i < sz; i++)	{		printf("%d", arr[i]);	}}void merge_sort(int arr[],int sz){	//開辟分配一個(gè)輔助臨時(shí)數(shù)組	int* temparr = (int*)mallco(sz * sizeof(int));	if (temparr)	{		//開辟成功之后 實(shí)現(xiàn)歸并之前的劃分?jǐn)?shù)組步驟		msort(arr,temparr, 0, sz - 1);		//利用之后 立刻釋放空間		free(temparr);	}	else//開辟失敗	{		printf("error:failed to allocate memory");	}}void msort(int arr[],int temparr[] ,int left, int right){	int mid = (left + right) / 2;//每一次找中間值 依次劃分	if(left <= right)	{		msort(arr,temparr, left,mid);//遞歸劃分后左邊的新一塊		msort(arr,temparr, mid + 1, right);//遞歸劃分后右邊的一塊		merge(arr, temparr, left, right, mid);//合并已劃分排序好的數(shù)組	}}void merge(int arr[], int temparr[], int left, int right, int mid){	//left一直為0	int L_pos = left;//標(biāo)記左半?yún)^(qū)第一個(gè)未排序的數(shù)字	int R_pos = right;//標(biāo)記右半?yún)^(qū)第一個(gè)未排序的數(shù)字	int pos = left;//臨時(shí)數(shù)組的下標(biāo)	while (L_pos <= mid && R_pos <= right)	{		//每次分別把左右半?yún)^(qū)的第一個(gè)元素拿出來(lái)進(jìn)行比較大小		if (arr[L_pos] > arr[R_pos])		{			temparr[pos] = arr[R_pos];			pos++;			R_pos++;		}		else		{			temparr[pos] = arr[L_pos];			pos++;			L_pos++;		}	}	//當(dāng)左半?yún)^(qū)排完之后 右半?yún)^(qū)剩余依次放進(jìn)去	while (L_pos <= mid)	{		temparr[pos] = arr[L_pos];		pos++;		L_pos++;	}	//同理可得	while (R_pos <= right)	{		temparr[pos] = arr[R_pos];		pos++;		R_pos++;	}	//把臨時(shí)數(shù)組合并后的元素放到原來(lái)的數(shù)組	while (left <= right)	{		//left在這同樣初始為0開始		arr[left] = temparr[left];		left++;	}}int main(){	int arr[] = { 9,5,2,7,12,4,3,1,11 };	int sz = sizeof(arr) / sizeof(arr[0]);	Print(arr, sz);	printf("/n");	merge_sort(arr,sz);	Print(arr, sz);	return 0;}

祝你好運(yùn)