分治法-合并排序

1.合并排序

排序算法是對一組數進行順序排序或者逆序排序，而合并排序就是排序算法的一種。合并排序用到了分治政策實作對元素進行排序。

合并排序的基本思想：把待排序的n個元素分解成n組，也就是每組一個元素；之後對分好的組進行兩兩合并（無配對的則不操作），以此類推。

以序列{8, 3, 2, 6, 7, 1, 5, 4}為例，排序過程如下：

排序過程

圖檔來源

合并排序又叫做2-路歸并排序，是因為它每次都是兩兩歸并。

/**
 * 合并src[left:mid] src[mid+1:right] 到dest[left:right]
 * @param src: 源數組
 * @param dest: 目的數組
 * @param left: 數組起始索引
 * @param mid: 源數組的中間索引
 * @param right: 目的數組的結束索引
*/
template<class Type>
void merge(Type src[], Type dest[], int left, int mid, int right) {
	//指針
	int i = left, j = mid + 1, k = left;
	//歸并
	while ((i <= mid) && (j <= right)) {
		if (src[i] <= src[j])
			dest[k++] = src[i++];
		else
			dest[k++] = src[j++];
	}
	//把剩下的數組元素拷貝到目的數組
	if (i > mid)
		for (int q = j; q <= right; q++)
			dest[k++] = src[q];
	else
		for (int q = i; q <= mid; q++)
			dest[k++] = src[q];
}
           

merge函數用于把src[left:mid] 和src[mid + 1: right]歸并到dest的對應位置。其思路如下

1. 設定兩個索引變量i和j儲存目前指向的src[left:mid] 和src[mid + 1: right]的索引；
2. 每次從i 和j 所指向的src[i] src[j]中取一個小值依次放到dest的對應位置，然後這個索引加一；
3. 重複2步驟直至周遊完短數組；
4. 把剩餘的值拼接到dest數組中。

/**
 * src[left:right]複制到dest[left:right]
 * @param src: 源數組
 * @param dest: 目的數組
 * @param left: 起始索引
 * @param right: 結束索引
*/
template<class Type>
void copy(Type src[], Type dest[], int left, int right) {
	while (left < right) {
		dest[left] = src[left];
		left++;
	}
}
           

copy的作用就是數組複制。

/**
 * 用于合并排序好的相鄰數組段
*/
template<class Type>
void mergePass(Type x[], Type y[], int step, int n) {
	int i = 0;
	while (i <= n - 2 * step) {
		merge(x, y, i, i + step - 1, i + 2 * step - 1);
		i = i + 2 * step;
	}
	if (i + step < n)
		merge(x, y, i, i + step - 1, n - 1);
	else
		for (int j = i; j < n ; j++)
			y[j] = x[j];
}
           

mergePass函數主要用于合并排序好的相鄰數組，

當step為1,時，此時數組被分成了n份，mergePass的while就是把上面的單個元素兩兩合并；

當step為2,時，則對最多為2個元素的子數組進行兩兩合并。

以此類推

在之後還有一個判斷：i + step < n，這裡舉例子來說明：

比如此時進行到了第二次歸并，即step = 2, 元素如下：

x = {1,2} {2, 3}, {1, 1} {4}

i = 0時，合并的是x[0: 1]和x[2:3],之後i = 0 + 2 * 2 = 4；

i = 4,時，得到i <= 7 - 2 * 2 = 3 不成立，是以不再循環。

雖然循環不成立，但是可以看到，{1, 1} {4}還是滿足i + step < n的，是以這裡又加了最後一個歸并。

而當x = {1, 2} {2, 3} {4}，step=2的情況下則會直接進行複制。
           

從上面的舉例可以看出，賦予step遞增的值，則可以實作歸并排序。

template<class Type>
void mergeSort(Type a[], int n) {
	Type* temp = new Type[n];
	int step = 1;

	while (step < n) {
		//合并到數組temp
		mergePass(a, temp, step, n);
		step += step;
		//合并到數組a
		mergePass(temp, a, step, n);
		step += step;
	}
	delete[] temp;
}
           

在mergeSort函數中，調用mergePass來實作歸并操作。

接着測試一下：

int main() {
	int a[] = {1, 4, 2, 6, 7, 5, 3};
	int len = sizeof(a) / sizeof(a[0]);
	//合并排序
	mergeSort(a, len);

	for (int i = 0; i < len; i++)
		cout << a[i] << " ";
	cout << endl;
	return 0;
}
           

2.自然合并排序

自然合并排序是上述所說的合并排序算法的一個變形。之前說過，合并排序是從一個元素開始兩兩歸并的，而當一個組内隻有一個元素時，能夠保證它是排序好的。基于上面的原理，給定一個數組，一般都會存在多個長度大于1的已自然排好序的子數組段。比如對于一個數組{1, 4, 2, 6, 7, 5, 3, 2}。自然排序的子數組段為{1, 4} {2, 6, 7} {5} {3} {2}；第一次排序可以得到{1, 2, 4, 6, 7} { 3, 5} {2}；第二次排序得到{1, 2, 3, 4, 5, 6, 7} {2} ；第三次排序則可以得到遞增序列。

上面需要解決的問題就是如何儲存每次的子數組段的開始和結束，因為子數組段的大小不是固定的，是以還需要一個數組去維護子數組的邊界。

template<class Type>
void mergeSort(Type a[], int len) {
	if (len == 0)
		return;
	//儲存子數組段的索引
	vector<int> indices(len + 1);
	indices[0] = -1;
	//indices中的真實個數
	int number = get_order(a, len, indices);
	Type* temp = new Type[len];
	number = indices.size();
	//自然歸并排序
	while (number != 2) {
		int index = 0;
		for (int i = 0; i + 2 < number; i += 2) {
			merge(a, temp, indices[i] + 1, indices[i + 1], indices[i + 2]);
		}
		//回寫到數組a
		for (int i = 0; i < len; i++)
			a[i] = temp[i];
		number = get_order(a, len, indices);
	}
	delete[] temp;
}
           

新的mergeSort函數用到了子數組段，其中維護了indices數組來存儲邊界，

首先可以看到indices的大小為len + 1,這是最壞情況下的indices的最大值，當數組完全逆序的時候，比如要把{5, 4, 3, 2, 1}排序成{1, 2, 3, 4, 5}時，我們可以一眼看出隻需要完全翻轉就可以了，不過程式則不知道，按照之前的步驟來說，以上分成了{5} {4} {3} {2} {1}共5個，再加上一開始的-1，是以最大數組長度設為了len + 1。

第一個元素為-1，主要是為了應對之後的排序。以{1, 4, 2, 6, 7, 5, 3, 2}為例子。自然排序的子數組段為{1, 4} {2, 6, 7} {5} {3} {2}；那麼indices的值為{-1, 1, 4, 5, 6, 7}。那麼需要a[-1 + 1: 1]和a[1 + 1, 4]進行歸并，a[4 +１: 5]和a[5 + 1:6]歸并...

每一次的循環都會重新擷取排序好的子數組段（其實可以從之前得到的）。

/**
 * 擷取數組a的自然排好序的子數組段，傳回結束索引
 * @param a: 數組
 * @param len: 數組a的長度
 * @param indices: 排序好的結束索引數組 需要確定長度足夠
 * @return: 傳回indices真正的長度
*/
template<class Type>
int get_order(Type a[], int len, vector<int>& indices) {
	int index = 1;
	int i = 1;
	while (index < len) {
		//記錄起點
		if (a[index] < a[index - 1]) {
			indices[i++] = index - 1;
		}
		index++;
	}
	indices[i++] = len - 1;
	return i;
}
           

根據mergeSort和get_order而得到的indices數組來說，必定存在的就是-1和最後一個元素的索引，是以當indices的實際個數為2的時候，表示排序結束。

3.測試

本測試在leetcode上執行，題目為：排序數組

普通歸并排序執行：

自然歸并排序執行：

可以看到，自然歸并排序的執行用時要小于普通歸并排序，不過記憶體消耗略微增加。

4.參考

• 書籍《計算機算法設計與分析 王曉東》
• 歸并排序三種實作方法（遞歸、非遞歸和自然合并排序）