归并排序及其优化(数组归并/链表归并，自顶向下/自底向上等)

2021.10.01

发布于未知归属地

归并排序时一种使用分治思想实现的高效的排序算法，它的最好/最坏/平均时间复杂度都是O(nlogn)，而且是一种稳定的排序算法。然而归并排序并没有得到广泛的应用，今天我们来看看归并排序的特点、优化和应用。

1. 算法简介

归并排序的原理
归并排序（Merge Sort）的核心思想就是一个典型的分治算法。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。算法示意图如下：

代码实现如下：

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
		int n = nums.size();
		temp.resize(n);
		mergeSort(nums, 0, n-1);
		return nums;
    }
private:
	vector<int> temp;
	void mergeSort(vector<int>& nums, int left, int right){
		if(left >= right) return;
		int mid = left+(right-left)/2;
		mergeSort(nums, left, mid);
		mergeSort(nums, mid+1, right);
		merge(nums, left, mid, right);
	}
	void merge(vector<int>& nums, int left, int mid, int right){
		for (int i = left; i <= right; ++i)
			temp[i] = nums[i];
		int i = left, j = mid+1, index = left;
		while(i <= mid && j <= right){
			if(temp[i] < temp[j])
				nums[index++] = temp[i++];
			else
				nums[index++] = temp[j++];
		}
		while(i <= mid)  nums[index++] = temp[i++];
		while(j <= right)  nums[index++] = temp[j++];
	}
};

由上面算法的实现我们可以看到，归并分解合并的过程就像一颗二叉树，树的高度是logn, 每层的合并时间复杂度是O(n)。归并算法的分解合并与数据是否有序无关，所以任何情况下的时间复杂度都是O(nlogn)。由于在合并的过程中使用了一个大小为n的临时数组，因此归并算法的空间复杂度是O(n)，非原地排序。与快速排序和堆排序相比，归并排序不是原地排序，这是归并排序的一大劣势，因而使用较少。

2.自底向上的归并算法

以上就是课本上经常讲的最典型的归并算法，由于依赖于递归实现，所以它是一种自顶向下的归并算法。
归并算法也可以不依赖递归，实现自底向上的归并。算法处理过程示意图如下：

自底向上的归并没有问题的分解过程，直接从元素数只有一个的问题开始，首先进行两两归并，然后四四归并，再之后八八归并，一直下去。
代码实现如下：

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
		int n = nums.size();
		temp.resize(n);
        for(int size = 1; size < n; size += size){
            for(int left = 0; left < n-size; left += size+size){
    		    merge(nums, left, left+size-1, min(left+size+size-1,n-1));
            }
        }
        return nums;
    }
private:
	vector<int> temp;
	void merge(vector<int>& nums, int left, int mid, int right){
		for (int i = left; i <= right; ++i)
			temp[i] = nums[i];
		int i = left, j = mid+1, index = left;
		while(i <= mid && j <= right){
			if(temp[i] < temp[j])
				nums[index++] = temp[i++];
			else
				nums[index++] = temp[j++];
		}
		while(i <= mid)  nums[index++] = temp[i++];
		while(j <= right)  nums[index++] = temp[j++];
	}
};

算法特点：
自底向上的归并算法也是使用分治思想解决问题，时间复杂度也是O(nlogn)，由于使用辅助数组存储空间复杂度也是O(n)。
与自顶向下的归并相比，自底向上的归并没有分解过程，不依赖与递归实现，不需要使用系统递归栈。所以虽然时间复杂度相同，但性能上自底向上的归并要优于自顶向下归并。

3.归并排序的优化

对小规模子数组使用插入排序，小规模范围内插入排序性能更优
测试子数组是否已经有序，如果有序则不需要合并

	void mergeSort(vector<int>& nums, int left, int right){
		if(left >= right) return;
		int mid = left+(right-left)/2;
		mergeSort(nums, left, mid);
		mergeSort(nums, mid+1, right);
        //测试子数组是否已经有序
        if(nums[mid] > nums[mid+1]){
    		merge(nums, left, mid, right);
        }
	}

不将元素复制到辅助数组

4.链表的归并排序（自顶向下）

148. 排序链表
题目描述：在O(nlogn) 时间复杂度内对链表排序
递归实现的自顶向下归并：

class Solution {
public:
    ListNode* sortList(ListNode* head) {
		return sortList(head, nullptr);
    }
private:
	ListNode* sortList(ListNode* head, ListNode* tail){
		if(!head) return head;
		if(head->next == tail){
			head->next = nullptr;
			return head;
		}
		ListNode* slow = head, *fast = head;
		while(fast != tail){
			slow = slow->next;
			fast = fast->next;
			if(fast != tail)
				fast = fast->next;
		}
		return merge(sortList(head,slow), sortList(slow,tail));
	}
	ListNode* merge(ListNode* list1, ListNode* list2){
		auto dummy = new ListNode(0);
		auto node = dummy;
		while(list1 && list2){
			if(list1->val < list2->val){
				node->next = new ListNode(list1->val);
				list1 = list1->next;
			}else{
				node->next = new ListNode(list2->val);
				list2 = list2->next;
			}
			node = node->next;
		}
		while(list1){
			node->next = new ListNode(list1->val);
			list1 = list1->next;
			node = node->next;
		}
		while(list2){
			node->next = new ListNode(list2->val);
			list2 = list2->next;
			node = node->next;
		}
		return dummy->next;
	}
};

算法分析：递归分治实现归并排序，时间复杂度O(nlogn)，虽然未使用额外存储，但递归会使用函数栈空间，空间复杂度O(logn)。

5. 链表的归并排序（自底向上）

148. 排序链表
题目描述：在O(nlogn)时间复杂度和常数空间复杂度内对链表排序
题目分析：为了实现O(1)空间复杂度，因此不能使用递归，使用自底向上的归并可以实现此目标。

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        int n = 0;
        auto node = head;
        while(node){
            node = node->next;
            n++;
        }
        auto dummy = new ListNode(0,head);
        for(int size = 1; size < n; size <<= 1){
            auto prev = dummy;
            auto cur = dummy->next;
            while(cur){
                //找到子链表的开始位置、中间位置和结束位置
                auto head1 = cur;
                for(int i = 1; i < size && cur->next; i++)
                    cur = cur->next;
                auto head2 = cur->next;
                cur->next = nullptr; //链表打断
                cur = head2;
                for(int i = 1; i < size && cur && cur->next; i++)
                    cur = cur->next;
                ListNode* next = nullptr; //子链表结尾后的位置
                if(cur){
                    next = cur->next;
                    cur->next = nullptr;//链表打断
                }
                //合并子链表
                auto temp = merge(head1, head2); 
                //挂接已排序子链表
                prev->next = temp;
                //移动prev和cur指针位置
                while(prev->next) prev = prev->next;
                cur = next;
            }
        }
		return dummy->next;
    }
private:
	ListNode* merge(ListNode* list1, ListNode* list2){
		auto dummy = new ListNode(0);
		auto node = dummy;
		while(list1 && list2){
			if(list1->val < list2->val){
				node->next = new ListNode(list1->val);
				list1 = list1->next;
			}else{
				node->next = new ListNode(list2->val);
				list2 = list2->next;
			}
			node = node->next;
		}
		while(list1){
			node->next = new ListNode(list1->val);
			list1 = list1->next;
			node = node->next;
		}
		while(list2){
			node->next = new ListNode(list2->val);
			list2 = list2->next;
			node = node->next;
		}
		return dummy->next;
	}
};