归并排序
一、认识
归并排序英文称为Merge Sort，归并排序是建立在归并操作上的一种有效的排序算法。归并排序有两种实现方法：自底向上和自顶向下。
特点:
- 稳定排序: 如果 a 原本在 b 的前面，且
a == b，排序之后 a 仍然在 b 的前面 - 非原地排序: 需要利用额外的数组来辅助排序。
- 排序方式: Out-place (占用额外内存)
- 时间复杂度: O(n) [n 代表数据规模及数据量大小]
- 空间复杂度: O(n)
扩展:
- 排序算法的稳定性:
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。
那么排序算法的稳定性有什么意义呢？其实它只在一种情况下有意义：当要排序的内容是一个对象的多个属性，且其原本的顺序存在意义时，如果我们需要在二次排序后保持原有排序的意义，就需要使用到稳定性的算法。
二、思想
归并排序思想:
将 1 个数字组成的有序数组合并成一个包含 2 个数字的有序数组，再将 2 个数字组成的有序数组合并成包含 4 个数字的有序数组...直到整个数组排序完成
2.1 自上而下
自上而下的方法是采用分治法思想，具体排序过程分成三个过程：
-
分解：将当前区间一分为二，即求分裂点
middle = (start + end)/2; -
求解：递归地对两个子区间
array[start,mid]和array[mid+1,end]进行归并排序；递归的终结条件：子区间长度为 1（一个记录自然有序）。 -
合并：将已排序的两个子区间
R[start,middle]和R[mid + 1..high]归并为一个有序的区间array[low..high]。
2.2 自下而上
自底向上方法，也就是常说的二路归并排序，其基本思想是：第 1 趟排序将长度为 n 的待排序记录看作 n 个长度为 1 的有序子序列，然后将这些子序列两两合并。完成第 1 趟排序之后，将得到 lgn 个长度为 2 的有序子序列（如果 n 为奇数，则最后还有一个长度为 1 的子序列）。第 2 趟排序是在第 1 趟的排序的基础上，将这 lgn 个长度为 2 的子序列两两合并。如此反复，直到最后得到一个长度为n的有序文件为止。从这个排序过程来看，二路归并排序是从将长度为 1 的子序列排序变化到长度为 n 的有序序列，因而是自底向上的。
三、实现
3.1 递归版 （自顶向下）
function merge(array, start, middle, end) {
let left = start;
let right = middle + 1;
let temp = [];
let t = 0;
while (left <= middle && right <= end) {
if (array[left] <= array[right]) {
temp[t++] = array[left++];
} else {
temp[t++] = array[right++];
}
}
while (left <= middle) {
temp[t++] = array[left++];
}
while (right <= end) {
temp[t++] = array[right++];
}
for (let i = 0; i < temp.length; i++) {
array[start++] = temp[i];
}
}
function mergeSort(array, start, end) {
if (start >= end) {
return;
}
let middle = (start + end) >> 1;
mergeSort(array, start, middle);
mergeSort(array, middle + 1, end);
merge(array, start, middle, end);
}
function sort(array) {
mergeSort(array, 0, array.length - 1);
}
const array = [3,2,1,5,4];
sort(array);
console.log(array);
3.2 迭代版（自底向上）
function merge(array, start, middle, end) {
let left = start;
let right = middle + 1;
let temp = [];
let t = 0;
while (left <= middle && right <= end) {
if (array[left] <= array[right]) {
temp[t++] = array[left++];
} else {
temp[t++] = array[right++];
}
}
while (left <= middle) {
temp[t++] = array[left++];
}
while (right <= end) {
temp[t++] = array[right++];
}
for (let i = 0; i < temp.length; i++) {
array[start++] = temp[i];
}
}
function mergeSort(array) {
let range = 1;
while (range < array.length) {
let i = 0;
for (i = 0; i < array.length - 2 * range; i += 2 * range) {
merge(array, i, i + range - 1, i + 2 * range - 1);
}
if (i + range < array.length) {
merge(array, i, i + range - 1, array.length - 1);
}
range *= 2;
}
}
function sort(array) {
mergeSort(array);
}