「排序算法」专题 3:归并排序(重点)
基本思路:借助额外空间,合并两个有序数组,得到更长的有序数组。例如:「力扣」第 88 题:合并两个有序数组。
算法思想:分而治之(分治思想)。「分而治之」思想的形象理解是「曹冲称象」、MapReduce,在一定情况下可以并行化。
个人建议:「归并排序」是理解「递归思想」的非常好的学习材料,大家可以通过理解:递归完成以后,合并两个有序数组的这一步骤,想清楚程序的执行流程。即「递归函数执行完成以后,我们还可以做点事情」。因此,「归并排序」我个人觉得非常重要,一定要掌握。
归并排序算法的基本实现(第 1 版)
这是我们首次接触递归算法的实现。下面我将一步一步展示如何编写递归函数实现归并排序。
第 1 步:先写出最顶层函数
我们对下标在 [0, len - 1]
,左闭且右闭的这个区间里的元素使用递归的「归并排序」算法。
/**
* 第 1 步:写出归并排序的外层框架
*/
@Test
public void test05() {
int[] arr = {8, 7, 6, 5, 4, 3, 2, 1};
int length = arr.length;
/**
* 我们对于归并排序的定义是左闭右闭的,所以第 3 个参数应该使用数组的长度 -1
*/
mergeSort(arr, 0, length - 1);
System.out.println(Arrays.toString(arr));
}
第 2 步:写出递归函数
注意应该先考虑递归终止的条件。
/**
* 第 2 步:实现归并排序算法(内层框架)这是顶向下的归并排序实现
* 递归调用的函数的定义是:对 arr 在 [left, right] 这个区间范围内使用归并排序
* 即对 arr 数组在索引 [left, right] 这个区间内的元素进行归并排序
* 特别注意:区间的边界 left 和 right 都是可以取到的
* @param arr 待排序数组
* @param left 闭区间端点
* @param right 闭区间端点
*/
private void mergeSort(int[] arr, int left, int right) {
// 当带排序的部分只有 1 个元素甚至更少的时候,归并排序就终止了,这一步很关键
// 使用递归进行代码实现的时候,递归到底的情况一定要考虑进来,否则递归就会无限进行下去,在逻辑上一定是错误的
// 先处理递归到底的情况,即递归终止条件:
// 1、不形成区间:left > right;
// 2、形成的区间长度为 1 :left = right,此时没有必要去"分",也无法"分"
if (left >= right) {
// 只有一个元素的时候,无需任何操作
return;
}
// 使用一分为二的思路,一直递归下去
// int mid = (left + right) / 2; 这种写法在 left 和 right 是大整数的时候,会发生溢出
int mid = left + (right - left) / 2;
// 下面这几行代码关于边界值的处理要特别小心,要紧扣自己定义的变量的含义进行逻辑的编写
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
mergeTwoSortedArray(arr, left, mid, right);
}
注意 1:首先处理递归到底的情况,这是很关键的:
if (left >= right) {
return;
}
注意 2:取中间值使用 int mid = left + (right - left) / 2;
这样可以避免使用 int mid = (left + right) / 2;
这种方式导致 left + right
越界的情况。
注意 3:下面两段代码第 3 行与第 1、2 两行的关系。
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
mergeTwoSortedArray(arr, left, mid, right);
还可以这样写:
mergeSort(arr, left, mid - 1);
mergeSort(arr, mid , right);
mergeTwoSortedArray(arr, left, mid - 1, right);
注意:应该准确理解 mergeTwoSortedArray
这个方法的含义,对于边界值的选择一定要紧扣我们设置的变量的含义。
第 3 步:编写 mergeTwoSortedArray
方法
我们要维护归并排序的定义,注意边界值。
/**
* 把两个已经排好序的数组进行合并
* 第 1 个数组:arr[left, ..., mid],是排好序的
* 第 2 个数组:arr[mid+1, ..., right],是排好序的
*
* @param arr 待排序数组
* @param left arr[left,mid] 已经是排好序的
* @param mid
* @param right arr[mid+1,right] 已经是排好序的
*/
private void mergeTwoSortedArray(int[] arr, int left, int mid, int right) {
// 首先计算出这个数组的长度
// 因为是左边闭区间,右边闭区间,所以元素的个数就是:右边界 - 左边界 + 1
int length = right - left + 1;
// 新建一个数组,赋值,用于比较
// 这里每进行一次比较,都要 new 一个数组,开销很大
int[] temp = new int[length];
// 为新数组赋值
for (int i = 0; i < length; i++) {
temp[i] = arr[left + i];
}
// 左边数组的起始位置
int l = 0;
// 右边数组的起始位置
int r = mid - left + 1;
// 循环遍历把 arr 在 [left, right] 这个区间重新赋值
// temp 数组中的元素不动,只是拿来做比较,然后我们一直修改的是 arr 数组在 [left, right] 的值
for (int i = 0; i < length; i++) {
// 先考虑如果左边数组用完(越界)的情况
if (l > mid - left) {
// 此时 l 遍历完成,就去拼命遍历 r 就好了
arr[i + left] = temp[r];
r++;
} else if (r > length - 1) {
// 此时 r 遍历完成,就去拼命遍历 l 就好了
arr[i + left] = temp[l];
l++;
} else if (temp[l] < temp[r]) {
arr[i + left] = temp[l];
l++;
} else {
arr[i + left] = temp[r];
r++;
}
}
}
Python 代码:
from sorting.examples import GenerateRandomArrayStrategy
from sorting.sorting_util import SortingUtil
class MergeSort:
def __str__(self):
return "归并排序"
def __merge_of_two_sorted_array(self, arr, left, mid, right):
# Python 中切片即复制,复制到一个临时数组中
nums_for_compare = arr[left:right + 1]
i = 0
j = mid - left + 1
# 通过 nums_for_compare 数组中设置两个指针 i、j 分别表示两个有序数组的开始
# 覆盖原始数组
for k in range(left, right + 1):
if i > mid - left:
arr[k] = nums_for_compare[j]
j += 1
elif j > right - left:
arr[k] = nums_for_compare[i]
i += 1
elif nums_for_compare[i] <= nums_for_compare[j]:
# 注意:这里使用 <= 是为了保证归并排序算法的稳定性
arr[k] = nums_for_compare[i]
i += 1
else:
assert nums_for_compare[i] >= nums_for_compare[j]
arr[k] = nums_for_compare[j]
j += 1
def __merge_sort(self, arr, left, right):
if left >= right:
return
# 这是一个陷阱,如果 left 和 right 都很大的话,left + right 容易越界
# Python 中整除使用 // 2
mid = (left + right) // 2
self.__merge_sort(arr, left, mid)
self.__merge_sort(arr, mid + 1, right)
self.__merge_of_two_sorted_array(arr, left, mid, right)
@SortingUtil.cal_time
def sort(self, arr):
"""
归并排序的入口函数
"""
size = len(arr)
self.__merge_sort(arr, 0, size - 1)
if __name__ == '__main__':
# 测试基本的归并排序算法正确
# SortingUtil.test_sorting_algorithm(MergeSort())
# 比较插入排序与归并排序,可以看出归并排序快很多
# SortingUtil.compare_sorting_algorithms(GenerateRandomArrayStrategy(),
# InsertionSortOptimizer(),
# MergeSort())
# 比较归并排序与归并排序的优化
# SortingUtil.compare_sorting_algorithms(GenerateRandomArrayStrategy(),
# MergeSort(),
# MergeSortOptimizer())
# 测试自底向上的归并排序
# SortingUtil.test_sorting_algorithm(MergeSortBU())
# 比较自顶向下的归并排序(递归实现)与自底向上的归并排序(循环实现)
# 自底向上的归并排序更耗时,因为分割不均匀
SortingUtil.compare_sorting_algorithms(GenerateRandomArrayStrategy(),
MergeSortOptimizer(),
MergeSortBU())
总结
基本的归并排序的思路其实并不难,可以使用规模较小的数组测试。
优化的方向
- 优化 1:在「小区间」里转向使用「插入排序」,Java 源码里面也有类似这种操作,「小区间」的长度是个超参数,需要测试决定,我这里参考了 JDK 源码;
- 优化 2: 在「两个数组」本身就是有序的情况下,无需合并;
- 优化 3:全程使用一份临时数组进行「合并两个有序数组」的操作,避免创建临时数组和销毁的消耗,避免计算下标偏移量。
- 注意:实现归并排序的时候,要特别注意,不要把这个算法实现成非稳定排序,区别就在
<=
和<
,已在代码中注明。
「归并排序」比「快速排序」好的一点是,它借助了额外空间,可以实现「稳定排序」,Java 里对于「对象数组」的排序任务,就是使用归并排序(的升级版 TimSort,在这里就不多做介绍)。
「归并排序」也有「原地归并排序」和「不使用递归」的归并排序,但是我个人觉得不常用,编码、调试都有一定难度。递归、分治处理问题的思想在基础算法领域是非常常见的,建议多练习编写「归并排序」学习递归思想,了解递归的细节,熟悉分治的思想。
经典问题
- 《剑指 Offer》第 51 题:数组中的逆序对,照着归并排序的思路就能写出来;
- 「力扣」第 315 题:计算右侧小于当前元素的个数,它们是一个问题。
(本节完)