《恋上数据结构与算法》排序（五）：归并排序

转载自 : https://blog.csdn.net/weixin_43734095/article/details/105127138

• 相关 : https://juejin.cn/post/6844904094235426830

一、经典十大排序算法

归并排序

• 归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

执行流程

• 不断地将当前序列平均分割成2个子序列，直到不能再分割。（序列中只剩1个元素）
• 不断地将2个子序列合并成一个有序序列，直到最终只剩下1个有序序列。

序列分割-divide

/**
 * 对[begin, end)范围的数据进行归并排序; 左闭右开
 *
 * @param begin
 * @param end
 */
private void divide(int begin, int end) {
    // 表示只有一个元素了, 就不需要归并排序
    if (end - begin > 1;
    // 归并排序左半子序列
    divide(begin, mid);
    // 归并排序右半子序列
    divide(mid, end);
    // 合并整个序列
    merge(begin, mid, end);
}

序列合并-merge 合并到新序列

• 将两个序列合并的思路为：左序列和右序列的中元素挨个比较，将较小的放入新序列中，最后新序列中的元素必然升序。

下图中 li，ri 分别代表指向左、右序列的元素索引，ai 为新序列（合并后的序列）的元素索引； 【li】代表左序列 li 位置的元素，【ri】代表右序列 ri 位置的元素，【ai】为新序列 ai 位置的元素；

• 第一轮：【li】 < 【ri】，【li】放入新数组，【ai】=【li】，li++; ai++;
• 第二轮：【li】 > 【ri】，【ri】放入新数组，【ai】=【ri】，ri++; ai++;
• 第三轮：【li】 < 【ri】，【li】放入新数组，【ai】=【li】，li++; ai++；
• 第四轮：左序列已经遍历完毕，直接将右序列剩余元素放入新序列，得到新序列（升序）。

原地合并-merge

• 将两个序列合并时，不一定要合并到新空间，可以合理的利用原空间实现 原地合并。

例如：

• 将 array的左半部分[begin, mid)，备份到 leftArray 中；
• 然后将 leftArray 视为左子序列，arrary的右半部分[mid, end] 视为右子序列；
• 将左子序列和右子序列合并到 array 中。

merge 过程：

• li < ri array[ai] = leftArray[li]； li++，ai++;
• li >= ri array[ai] = array[ri]; ri++，ai++;

对序列 { 3, 8, 6, 10 } 进行归并排序：

对序列 { 3, 6, 8, 10 } 进行归并排序：左子序列先遍历结束，那就归并结束。 对序列 { 8, 10, 3, 6 } 进行归并排序：右子序列先结束，则将左边剩余全部放入。

原地合并-merge-实现

/**
 * 将 [begin, mid) 和 [mid, end) 范围的序列合并成一个有序序列
 */
private void merge(int begin, int mid, int end){
	int li = 0, le = mid - begin; // 左边数组(基于leftArray)
	int ri = mid, re = end;	// 右边数组(array)
	int ai = begin; // array的索引
	
	// 备份左边数组到leftArray
	for(int i = li; i