歸并排序算法流程

歸并排序算法原理：

相較于快速排序，歸并排序主要應用于總體無序，但各子數列有序的數組排序，其算法思想為：将待排數列分為若幹子數列，先使各子數列有序，然後将各子數列合并為一個有序數列，詳細的歸并算法流程為：

1. 取待排序數組q[]的中間點為分界點x=mid=(l+r)/2 ，分成left區域和right區域，遞歸排序left數組和right數組；
2. 使用雙指針算法将上面兩個子數組進行合并；其中雙指針算法的詳細合并流程為：

• 因為上面left數組和right數組的數都是按照從小到大排好序的數組，通過設定兩個指針，使這兩個指針分别指向這兩個數組中的min值，比較這兩個min值的大小，将較小者放入新建立的數組ans[]中用來記錄答案，同時該指針向後移動一位；直到有一數組為空，并将另一非空數組中所有的數直接寫入ans[]中 。

歸并排序的代碼實作：

//C++實作
#include<iostream>
using namespace std;
const int N = 1000010;

int n;
int q[N], ans[N];  //定義兩個數組，q[N]用來存儲待排序數組，ans[N]用來存儲經歸并排序的數組

void merge_order(int q[], int l; int r){      //q[]時用來排序的數組，l是數組的左邊界，r是數組的右邊界，閉區間
	if(l <= r) return;                         //如果數組中沒數或者隻有一個數，則直接傳回
	int mid = (l + r) >> 1;                    //第一步，取中間點為分界點，
	merge_order(q, l , mid), merge_order(q, mid +1, r);     //遞歸排序mid的left數組和right數組
	int k = 0, i = 1, j = mid +1;                           //用i和j兩個指針分别指向兩個數組中的min值
	while(i <= mid && j <= r){                              //比較兩個min值的大小，并将其中的較小者放入新建立的數組ans[]中，直到有一數組為空，則終止循環
		if(q[i] <= q[j]) ans[k++] = q[i++];
		else ans[k++] = q[j++];
	}
	while(i <= mid) ans[k ++] = q[i ++];              //将不空數組中的所有數直接寫入ans[]中
	while(j <= r) ans[k++] = q[j++];
	for(i = l, j = 0;i <= r;i ++, j ++) q[i] = ans[j]; //将ans[]中的數再傳入q[l~r]中，注意i是從l開始的
}

int main(){
	scanf("%d",&n);
	for(int i = 0;i < n;i++) scanf("%d",&q[i]);

	merge_order(q, 0, n - 1);
	for(int i = 0;i < n;i++) printf("%d",q[i]);
	return 0;
}