归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:
- 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);
- 自下而上的迭代;
在《数据结构与算法 JavaScript 描述》中,作者给出了自下而上的迭代方法。但是对于递归法,作者却认为:
However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle. 然而,在 JavaScript 中这种方式不太可行,因为这个算法的递归深度对它来讲太深了。
说实话,我不太理解这句话。意思是 JavaScript 编译器内存太小,递归太深容易造成内存溢出吗?还望有大神能够指教。
和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。
1. 算法步骤
- 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
- 设定两个指针,最初位置分别为两个已经排序序列的起始位置;
- 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
- 重复步骤 3 直到某一指针达到序列尾;
-
2. 图解
3. Java 代码实现
public class MergeSort {
private static void mergeSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int index = (left + right) / 2;
mergeSort(arr, left, index);
mergeSort(arr, index + 1, right);
merge(arr, left, right);
}
private static void merge(int[] nums, int left, int right) {
int mid = (left + right) / 2;
int[] tmp = new int[right - left + 1];
int i = left, j = mid + 1, cur = 0;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
tmp[cur++] = nums[i++];
} else {
tmp[cur++] = nums[j++];
}
}
for (; i <= mid; i++) {
tmp[cur++] = nums[i];
}
for (; j <= right; j++) {
tmp[cur++] = nums[j];
}
cur = 0;
for (int k = left; k <= right; k++) {
nums[k] = tmp[cur++];
}
}
}