C語言——?dú)w并排序-創(chuàng)新互聯(lián)

C語言——?dú)w并排序

歸并排序用到了分治思想，借助遞歸的方式對一串?dāng)?shù)字進(jìn)行排序，整個過程分為分開和合并兩個過程。其實(shí)歸并排序的思想并不難理解，但是用代碼實(shí)現(xiàn)它卻并不容易，我們要寫兩個函數(shù)去分別實(shí)現(xiàn)這個過程，一個函數(shù)用來專門分開合并，另一個函數(shù)則描述了每一次排序的過程。
我們來看一個例子：

在臨夏州等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都網(wǎng)站建設(shè)、成都網(wǎng)站制作 網(wǎng)站設(shè)計制作按需定制開發(fā),公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站設(shè)計,成都全網(wǎng)營銷推廣,成都外貿(mào)網(wǎng)站建設(shè)公司,臨夏州網(wǎng)站建設(shè)費(fèi)用合理。
a[]={1,3,5,7,2,4,6,8};

對于這個數(shù)組，利用歸并的思想排序，就是把它分成兩個部分，從中間截開，分成兩組數(shù)：1，3，5，7和2，4，6，8；我們可以發(fā)現(xiàn)兩組數(shù)都是從小到大排序的，我們可以定義兩個變量一個指向前一串?dāng)?shù)的第一個數(shù)字，另一個變量指向第二組數(shù)的第一個變量，分別比較這兩個數(shù)，將小的那個放進(jìn)一個新數(shù)組，然后變量往后移，逐個比較，最終就有了一個新數(shù)組，這個新數(shù)組就是排序好的數(shù)組。
但是如果分成兩組數(shù)之后，兩邊的數(shù)字并不是有序的該怎么辦？這時候說明把數(shù)組分開一次不夠，就要繼續(xù)再分，如果還不是有序的？再分，直到把它們分為一個一個的數(shù)，然后再用歸并的思想把它們重新排回原來的數(shù)組，整個數(shù)組就變得有序了。
在這里可能不太好理解，我們可以看一下下面的圖片，或許就好理解很多。
在這里插入圖片描述
接下來我們來看代碼，首先我們來看第一個函數(shù)，第一個函數(shù)的作用就是把數(shù)組從中間切開再合并。

void merge_sort(int a[],int left,int right){if(leftint mid = (left + right) / 2;//從中間截開
		merge_sort(a,left, mid);//把左邊沿中間截開
		merge_sort(a, mid + 1, right);//把右邊沿中間截開
		merge(a, left, right, mid);//合并
	}
}

接下來這個函數(shù)是合并的過程。

void merge(int a[],int left,int right,int mid) {int s[100];//一個新數(shù)組用來存儲排序好的數(shù)組
	int i = left, j = mid + 1;//兩個變量分別指向左邊和右邊兩組數(shù)的第一個數(shù)
	int sor = left;
	while (i<= mid && j<= right) {if (a[i]< a[j]) {//歸并的過程
			s[sor++] = a[i++];
		}
		else {	s[sor++] = a[j++];
		}
	}
	while (i<= mid) s[sor++] = a[i++];//當(dāng)一組數(shù)已經(jīng)全部排進(jìn)去之后，再將另外一組數(shù)的全部數(shù)字都排進(jìn)去
	while (j<= right)  s[sor++] = a[j++];
	sor = left;
	while (sor<= right) {//把排好序的新數(shù)組全部放回原數(shù)組里
		a[sor] = s[sor];
		sor++;
	}
}

我們在主函數(shù)運(yùn)行一下這個代碼。

#includevoid merge_sort(int a[],int left,int right){if(leftint mid = (left + right) / 2;
		merge_sort(a,left, mid);
		merge_sort(a, mid + 1, right);
		merge(a, left, right, mid);
	}
}
void merge(int a[],int left,int right,int mid) {int s[100];
	int i = left, j = mid + 1;
	int sor = left;
	while (i<= mid && j<= right) {if (a[i]< a[j]) {	s[sor++] = a[i++];
		}
		else {	s[sor++] = a[j++];
		}
	}
	while (i<= mid) s[sor++] = a[i++];
	while (j<= right)  s[sor++] = a[j++];
	sor = left;
	while (sor<= right) {a[sor] = s[sor];
		sor++;
	}
}
int main()
{int a[]={3,9,5,4,64,4,5,9,8,9};
 	int i;
 	merge_sort(a, 0, 9);
 	for(i = 0; i< 10; i++)
	{printf("%d ", a[i]);
	}
 	return 0; 
}

運(yùn)行結(jié)果：
在這里插入圖片描述

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前名稱：C語言——?dú)w并排序-創(chuàng)新互聯(lián)
文章鏈接：http://www.muchs.cn/article2/dhceic.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站制作、網(wǎng)站導(dǎo)航、網(wǎng)站排名、網(wǎng)頁設(shè)計公司、移動網(wǎng)站建設(shè)、搜索引擎優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

成都做網(wǎng)站