C語言——歸并排序

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

在臨夏州等地區，都構建了全面的區域性戰略布局，加強發展的系統性、市場前瞻性、產品創新能力，以專注、極致的服務理念，為客戶提供成都網站建設、成都網站制作 網站設計制作按需定制開發,公司網站建設,企業網站建設,品牌網站設計,成都全網營銷推廣,成都外貿網站建設公司,臨夏州網站建設費用合理。

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

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

接下來我們來看代碼，首先我們來看第一個函數，第一個函數的作用就是把數組從中間切開再合并。

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);//合并
	}
}

接下來這個函數是合并的過程。

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

我們在主函數運行一下這個代碼。

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

運行結果：

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

當前名稱：C語言——歸并排序-創新互聯
文章鏈接：http://m.newbst.com/article2/dhceic.html

成都網站建設公司_創新互聯，為您提供網站制作、網站導航、網站排名、網頁設計公司、移動網站建設、搜索引擎優化

廣告

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