归并排序及其空间复杂度的思考

淡淡的烟草味﹌ 2022-08-06 04:12 154阅读 0赞

归并排序采用分治的方法。

对归并排序来说：

如果对Merge的每个递归调用都声明一个临时数组，那么任一时刻可能会有logN个临时数组处于活动期,这对小内存机器是致命的。另一方面，如果Merge动态分配并释放最小量临时空间，那么由malloc占用的时间会很多。由于Merge位于MSort的最后一行，可以在MergeSort中建立该临时数组。因此在任一时刻只需要一个临时数组活动，而且可以使用该临时数组的任意部分；我们将使用和输入数组array相同的部分。这样的话，该算法的空间占用为N，N是待排序的数组元素个数。

/*
    tmp_array[]：辅助数组。
    left_pos：数组左半部分的游标
    left_end：左边数组的右界限
    */
    void Merge(int array[], int tmp_array[], int left_pos, int right_pos, int right_end) {
    	int i, left_end, num_elements, tmp_pos;
    	left_end = right_pos - 1;
    	tmp_pos = left_pos;
    	num_elements = right_end - left_pos + 1;
    
    	while (left_pos <= left_end && right_pos <= right_end)
    		if (array[left_pos] <= array[right_pos])
    			tmp_array[tmp_pos++] = array[left_pos++];
    		else
    			tmp_array[tmp_pos++] = array[right_pos++];
    	while (left_pos <= left_end)
    		tmp_array[tmp_pos++] = array[left_pos++];
    	while (right_pos <= right_end)
    		tmp_array[tmp_pos++] = array[right_pos++];
    	for (i = 0; i < num_elements; i++, right_end--)
    		array[right_end] = tmp_array[right_end];
    }
    
    void MSort(int array[], int tmp_array[], int left, int right) {
    	int center;
    	if (left < right) {
    		center = (left + right) / 2;
    		MSort(array, tmp_array, left, center);
    		MSort(array, tmp_array, center + 1, right);
    		Merge(array, tmp_array, left, center + 1, right);
    	}
    }
    
    void MergeSort(int array[], int n) {
    	int *tmp_array;
            //上面文字部分给出了为什么在MergeSort中建立临时数组tmp_array
            tmp_array = (int *)malloc(n * sizeof(int));
    	if (tmp_array != NULL) {
    		MSort(array, tmp_array, 0, n - 1);
    		free(tmp_array);
    	}
    	else
    		cout << "malloc failed" << endl;
    }

虽然归并排序的时间为O(NlogN)，但是它 很难用于主存排序，因为合并两个排序的表需要线性附加内存，整个算法中还要花费将数据拷贝到临时数组再拷贝回来这样的附加工作，这严重影响排序的速度。

**对于重要的内部排序应用而言，往往选择快速排序。合并的方法是大多数外部排序算法的基石**。

\------------------------------------------------------分割------------------------------------------------------------------

空间复杂度为o(1)的归并排序代码：github（[点击打开链接][Link 1]）

摘录如下：

//空间复杂度为O(1)的归并排序
    #include <iostream>
    using namespace std;
    
    void reverse_array(int a[], int n) {
    	int i = 0;
    	int j = n - 1;
    	while (i < j) {
    		swap(a[i], a[j]);
    		++i;
    		--j;
    	}
    }
    
    void exchange(int a[], int length, int length_left) {
    	reverse_array(a, length_left);
    	reverse_array(a + length_left, length - length_left);
    	reverse_array(a, length);
    }
    
    void Merge(int a[], int begin, int mid, int end) {
    	while (begin < mid && mid <= end) {
    		int step = 0;
    		while (begin < mid && a[begin] <= a[mid])
    			++begin;
    		while (mid <= end && a[mid] <= a[begin]) {
    			++mid;
    			++step;
    		}
    		exchange(a + begin, mid - begin, mid - begin - step);
    	}
    }
    void MergeCore(int a[], int left, int right) {
    	if (left < right) {
    		int mid = (left + right) / 2;
    		MergeCore(a, left, mid);
    		MergeCore(a, mid + 1, right);
    		Merge(a, left, mid + 1, right);
    	}
    }
    void MergeSort(int a[], int length) {
    	if (a == NULL || length < 1)
    		return;
    	MergeCore(a, 0, length - 1);
    }
    
    int main() {
    	int a[] = {1,0,2,9,3,8,4,7,6,5,11,99,22,88,11};
    	int length = sizeof(a) / sizeof(int);
    	MergeSort(a, length);
    	
    	for (int i = 0; i < length; i++)
    		cout << a[i] << " ";
    	cout << endl;
    	return 0;
    }

下面的文章给出了[在空间复杂度O(1)的条件下实现归并排序][O_1]

原文如下：

第一：对一个L1,L2,的子序列，分别长度为，m,n.可以用min(m,n)的空间协助进行归并排  
序，且仅对该额外空间的值得顺序有影响。详细参见sara basse的那本算法书.

第二：对于一个已经排序的L1,L2,总长度假定为u,为了方便分析,假定L1的长度=L2的长度=u/2,切分成sqrt(u)的个  
块，每个快有sqrt(u)个数，然后对L1,的最后一块和L2的最后一块归并，L2的最后一  
块存放全部数据的最大数据，同时也是利用L2的这个最后一块作为下面归并的额外空间。

第三：对剩余的块(除L2最后一块,那块存放最大元素的那块),按照块的最小元素排序，之后依次归并相邻块。

第四：对最后一块进行排序，因为他作为额外空间，参与了两两相邻的块排序,自己的顺序不能保证,所以最后还要排序一次。

这种方法的正确性可以这样来简单解释

由于最后的分块都是从L1或者L2中切下来的。

那么第i块，第i+1块和第i+2块（如果按照最小元素排序的话）

不妨假定第i块来自L1，第i+1块来自L2。（i，i+1，i+2，是切下来后的编号，例如例子中第1块是1 4 6 15是L1的第一块，第2块2 3 4 16是L2的第1块）

**那么i+2块可能来自哪里呢？要么是原L1块在第i块后面，要么是原L2块在i+1块后面的块。也就是第i+1块至少比N个数要大（N为块内数目），换言之i和i+1块归并后的最小块i'块均比i+1块小，这一点是本算法的难点，想明白后，就不难理解了。**

因此i和i+1这两块归并后的i‘块的最大元素，一定比i+1块的最小元素要小，因此正确性可以保证。

画个图来举例：

![0_1281400661R8Tw.gif][]

![0_1281403868Lm8P.gif][]

图1 通过对L1和L2的最大块进行归并，用一个4个元素的交换空间，得到L1&L2的最大块22 23 24 25

![0_128140336677Cv.gif][]

图2 将归并顺序按照块最小元素的顺序进行归并，并利用交换空间

![0_1281403605Ut53.gif][]

图3 利用交换空间归并的过程，注意归并后交换空间的数依然是22 23 24 25，但顺序已经变了，因此在归并到最后还需要再排序一次

4 5 6 15 和 16 17 20 21的归并不再图示。

[Link 1]: https://github.com/liyangddd/algorithms/blob/master/7mergesort_improved.cpp
[O_1]: http://blog.csdn.net/pennyliang/article/details/1269165
[0_1281400661R8Tw.gif]: /images/20220806/d56dac14564348728c502eaf7f461ce5.png
[0_1281403868Lm8P.gif]: /images/20220806/7d69ff5be870442c85c434bc4a91b724.png
[0_128140336677Cv.gif]: /images/20220806/d32a4746e4b848fd80b1d10b58d91d41.png
[0_1281403605Ut53.gif]: /images/20220806/f31d9f03695f44f990af81ef443e2702.png