歸并排序

遞歸的函數

void sort(int l, int r)

{

if(l<r)

{int m=(l+r)/2;

sort(l,m);//左面

sort(m+1,r);//右邊

merge(l,m,r);

}}

1、随機給數組一排數字 把它存進全局數組arr[]中。

2、裡面有6個數，我們定義一個 int m作為中間數值為 m=(l+r)/2 ,也就是m=(0+6)/2  ，這個m是作為中間數，我們把左面的設一個變量 int l, 右面設的變量為 int r。

3、我們看函數一步一步走 if(l<r)成立 ，往下 m=(l+r)/2  l為0，r為6 m=3 ,進左遞歸 sort(l,m);//左面，參數l,m 0和3傳進去 遞歸第二層中 l為0，r=3。

第二層中  if(i<r)依然成立，繼續 m=(0+3)/2 這裡我們把m 4舍5入 為2，接着進左遞歸 sort(l,m);//左面 l,m 0和2傳進去  遞歸第三層中 l為0，r=2。

第三層中 if(i<r)還是成立，m=(0+2)/2  m這次為零了 ，繼續進左遞歸 sort(l,m);//左面  l,m 0和0傳進去 遞歸第四層 ，l為0，r也為0。if(i<r)不成立，包含的内容不執行，此時遞歸可算到頭了。傳回到遞歸的上一層，執行sort(l,m);//左面  下面的sort(m+1,r);//右邊

此層m為2，r為3  m+1,r 作為參數傳遞給sort(m+1,r);//右邊 接着判斷然後接着................................................

這裡一張流程圖概括

4、如果遞歸明白了，就需要我們排序合并。

排序合并排序

void merge(int z,int m,int y)

{  int i=z, j=m+1,k=z;

    while(i<=m&&j<=y)

      if(arr[i]<arr[j])

        arr1[k++]=arr[i++];

    else

       arr1[k++]=arr[j++];

 while(i<=m)

    arr1[k++]=arr[i++];

while(j<=y)

    arr1[k++]=arr[j++];

for(i=z;i<y;i++)

{arr[i]=arr[i];

}}

    因為merge函數是在 sort(l,m)和sort(m+1,r)的下面，然後我們回頭看遞歸中最後一層是哪一層？ 是第三層，第三層的 l為0，m為0，r為2帶入merge函數中

這裡用到了輔助 數組arr1[]來暫時存放通過比較後放入的資料。參數 int z是左 ，int m是中 ，int y是右。

定義變量進行參數的指派  int i=z, j=m+1,k=z 。

while(i<=m&&j<=y) i從左開始到arr數組中間m , j從中間加一的位置開始到arr數組的右邊。

if(arr[i]<arr[j]) 開始比較。

小的放前面 2和1 小的放到arr1中。

    arr1[k++]=arr[i++];

    else

    arr1[k++]=arr[j++];    

下面兩個while循環是對左右作比後避免出現左右比較數有剩餘的情況。

while(i<=m)   

    arr1[k++]=arr[i++];

while(j<=y)

    arr1[k++]=arr[j++];

然後下面的for循環是對arr1數組中暫存的資料再指派給arr數組中。

for(i=z;i<y;i++)

{arr[i]=arr[i];

}}  

這一層的merge執行完成之後回到上一層執行sort(m+1,r)函數内部的内容，然後再次傳回上一層。

排序歸并過程總覽圖    

根據上圖參照的來看，計算機的執行過程大體是這樣。                                                                                                                                                        

程式代碼

#include <iostream>
#include <stdio.h>

using namespace std;
int a[10] = { 2,3,4,1,2,3,1,2,1,5 };
int b[10];
void merge(int a[], int b[], int z, int m, int y) {
	int i = z;
	int j = m + 1;
	int k = z;
	int q;
	while (i <= m && j <= y)
		if (a[i] < a[j])
			b[k++] = a[i++];
		else
			b[k++] = a[j++];

	if (i <= m)
		for (q = i; q <= m; q++)
			b[k++] = a[i++];
	else
		for (q = j; q <= y; q++)
			b[k++] = a[j++];
}
void copy(int a[], int b[], int l, int r)
{
	int i;
	for (i = l; i <= r; i++)
		a[i] = b[i];

}

void sort(int a[], int l, int r)

{
	if (l < r)
	{

		int m = (l + r) / 2;
		sort(a, l, m);
		sort(a, m + 1, r);
		merge(a, b, l, m, r);
		copy(a, b, l, r);
	}
}

int main() {

	sort(a, 0, 9);
	for (int i = 0; i < 10; i++)
		cout<<("%d", a[i]);
}