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

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

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

a[]={1,3,5,7,2,4,6,8};

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

接下來(lái)我們來(lái)看代碼，首先我們來(lái)看第一個(gè)函數(shù)，第一個(gè)函數(shù)的作用就是把數(shù)組從中間切開(kāi)再合并。

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

接下來(lái)這個(gè)函數(shù)是合并的過(guò)程。

void merge(int a[],int left,int right,int mid) {int s[100];//一個(gè)新數(shù)組用來(lái)存儲(chǔ)排序好的數(shù)組
	int i = left, j = mid + 1;//兩個(gè)變量分別指向左邊和右邊兩組數(shù)的第一個(gè)數(shù)
	int sor = left;
	while (i<= mid && j<= right) {if (a[i]< a[j]) {//歸并的過(guò)程
			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++;
	}
}

我們?cè)谥骱瘮?shù)運(yùn)行一下這個(gè)代碼。

#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級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章標(biāo)題：C語(yǔ)言——?dú)w并排序-創(chuàng)新互聯(lián)
標(biāo)題鏈接：http://weahome.cn/article/dhceic.html