排序算法之歸并排序

一、基本思想

歸并排序，和快排一樣同樣采用了分治的思想，将兩個（或以上）有序表合并成一個新的有序表。

歸并排序步驟如下：

1. 把N個記錄看成 N個長度為 1 的有序子表；
2. 進行兩兩歸并使記錄關鍵字有序，得到 N/2 個長度為 2 的有序子表； 
3. 重複第2步直到所有記錄歸并成一個長度為N的有序表為止。

二、算法實作

下面是歸并排序算法的 遞歸實作：

#include <iostream>
#include <malloc.h>
using namespace std;

// 合并兩個有序部分
void mergeArray(int a[], int first, int mid, int last, int temp[]) {
	if (first >= last) {
		return;
	}
	int i = first, j = mid + 1;
	int k = first;
	while (i <= mid && j <= last) {
		if (a[i] > a[j]) {
			temp[k++] = a[j++];
		} else {
			temp[k++] = a[i++];
		}
	}
	while (i <= mid) {
		temp[k++] = a[i++];
	}
	while (j <= last) {
		temp[k++] = a[j++];
	}

	// 回寫到原來數組中
	for (k = first; k <= last; k++) {
		a[k] = temp[k];
	}
}

// 遞歸調用歸并
void mSort(int* a, int first, int last, int *temp) {
	if (first < last) {
		int mid = (first + last) >> 1;
		mSort(a, first, mid, temp);
		mSort(a, mid + 1, last, temp);
		mergeArray(a, first, mid, last, temp);
	}
}

// 歸并排序算法
void mergeSort(int *a, int len) {
	int* temp = (int*) malloc(len * sizeof(int));
	mSort(a, 0, len - 1, temp);
	free(temp);
}

int main() {
	int arr[] = { 213, 43, 43, 123, 45, 52, 67, 234, 452, 5, 67 };
	int len = 11;

	cout << "Before sorting:" << endl;
	for (int i = 0; i < len; i++) {
		cout << arr[i] << "\t";
	}

	mergeSort(arr, len);

	cout << endl << "After merge sorting:" << endl;
	for (int i = 0; i < len; i++) {
		cout << arr[i] << "\t";
	}
	cout << endl;

	return 0;
}
           

三、算法分析

歸并排序最好、平均、最壞時間複雜度都是：O(n*log2(n))，

歸并排序需要額外的存儲空間，其空間複雜度為：O(n).

歸并排序和快排、堆排序一樣是一種高效的排序算法，在資料規模較大而且存儲空間要求足夠的情況下是非常好的選擇。

四、算法改進

歸并排序改進和優化的方向如下：

• 當問題分割很小到某個規模的時候停止遞歸，采用簡單插入排序；
• 消除遞歸調用
• 消除反複回寫
• ...

下面是改進的一個消除遞歸算法：

#include <iostream>
#include <malloc.h>
using namespace std;

// 合并數組中連續的兩個有序部分
void mergeArray(int a[], int first, int mid, int last, int temp[]) {
	int i = first, j = mid + 1;
	int k = first;
	while (i <= mid && j <= last) {
		if (a[i] > a[j]) {
			temp[k++] = a[j++];
		} else {
			temp[k++] = a[i++];
		}
	}
	while (i <= mid) {
		temp[k++] = a[i++];
	}
	while (j <= last) {
		temp[k++] = a[j++];
	}
}

// 根據設定的步長來順序歸并
void mergeStep(int a[], int step, int len, int temp[]) {
	int first, mid, last;
	first = 0;
	last = first + step + step - 1;
	mid = first + step - 1;
	while (last < len) {
		mergeArray(a, first, mid, last, temp);
		first = last + 1;
		last = first + step + step - 1;
		mid = first + step - 1;
	}
	// 末端注意數組邊界
	if (mid > len) {
		for (int i = first; i < len; i++) {
			temp[i] = a[i];
		}
	} else {
		mergeArray(a, first, mid, len - 1, temp);
	}
}

void mergeSort(int a[], int len) {

	cout << "Before sorting:" << endl;
	for (int i = 0; i < len; i++) {
		cout << a[i] << "\t";
	}
	cout << endl;
	//
	int flag = 0; // 寫入方向辨別
	int* temp = (int*) malloc(len * sizeof(int));
	// 消除遞歸
	for (int step = 1; step < len; step = step << 1) {
		// 避免傳回回寫
		if (flag++ % 2) {
			// flag初始為奇數，向a寫入排序結果，執行後flag為偶數
			mergeStep(temp, step, len, a);
		} else {
			// flag初始為偶數，向temp寫入即可,執行後flag為奇數
			mergeStep(a, step, len, temp);
		}
	}
	// 若flag為奇數，則表明排序結果存在于temp中，需要回寫
	if (flag % 2) {
		for (int i = 0; i < len; i++) {
			a[i] = temp[i];
		}
	}
	//
	free(temp);
	//
	cout << "After merge sorting:" << endl;
	for (int i = 0; i < len; i++) {
		cout << a[i] << "\t";
	}
	cout << endl;

}

int main() {
	int arr[17] = { 213, 67, 89, 10, 23, 9, 23, 45, 12, 456, 234, 67, 12, 0 };
	int len = 17;
	mergeSort(arr, len);
	return 0;
}