(四)前端javascript中的数据结构之归并排序
//归并排序的特点
// 1.归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
// 2.归并排序是一种稳定的排序方法。
// 3.归并排序是建立在归并操作上的一种有效的排序算法。归并操作（merge）指的是将两个有序的序列合并成一个有序序列的过程。
// 4.归并排序是一种时间复杂度为O(nlogn)的排序算法。
// 5.归并排序是一种稳定的排序方法。
function mergeSort(arr) {
return mergeSortRecursion(arr);
}
function mergeSortRecursion(arr, type) {
//如果数组长度小于等于1，直接返回
if (arr.length <= 1) return arr;
//计算中间值
var mid = Math.floor(arr.length / 2);
//拆分数组,为左右两部分,并递归
var leftArr = arr.slice(0, mid);
console.log("???? ~ mergeSortRecursion ~ leftArr:", leftArr);
var rightArr = arr.slice(mid);
console.log("???? ~ mergeSortRecursion ~ rightArr:", rightArr);
console.log("???? ~ mergeSortRecursion ~ type:", type);
console.log("aaa");
return merge(
mergeSortRecursion(leftArr, "left"),
mergeSortRecursion(rightArr, "right")
);
}
function merge(left, right) {
console.log("???? ~ merge ~ right:", right);
console.log("???? ~ merge ~ left:", left);
let result = [],
il = 0,
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++]);
}
console.log("???? ~ merge ~ result:", result);
return result;
}