归并排序是一种分治算法.思想是把原数组切分成较小的数组,直到每个小数组只有一个位置,再将小数组归并成较大的数组,直到最后有一个完整有序的大数组.
js 实现如下:
归并排序是一种稳定排序,无论最好情况和最坏情况时间复杂度为 O(nlogn),空间复杂度为 O(n).
function mergeSort(arr) {
if (arr.length == 1) {
return arr; //长度为1直接返回
} else if (arr.length == 2) {
var ar0 = arr[0];
var ar1 = arr[1];
arr[0] = ar0 <= ar1 ? ar0: ar1;
arr[1] = ar0 > ar1 ? ar0: ar1; //长度为2,返回排好序的数组
} else {
var mid = Math.floor(arr.length / 2);
var left = mergeSort(arr.slice(0, mid));
var right = mergeSort(arr.slice(mid, arr.length)); //递归
var result = [];
var il = 0;
var ir = 0;
while (il < left.length && ir < right.length) {
if (left[il] <= right[ir]) {
result.push(left[il++]);
} else {
result.push(right[ir++]);
}
} //合并
while (il < left.length) {
result.push(left[il++]);
} //左边的数组未拍完,直接添加在数组末尾
while (ir < right.length) {
result.push(right[ir++]);
} //右边的数组未拍完,直接添加在数组末尾
//以上两个至多有一个会发生
return result;
}
}
附:T(n)=2T(n/2)+cn;
T(n)=4T(n/4)+2cn;
T(n)=8T(n/8)+3cn;
n=2^k;
k=log2 n;
T(n)=2^kT(n/2^k)+kcn;T(n)=nT(1)+cnlog2n;
来源: http://www.bubuko.com/infodetail-2461677.html