佛山哪个做网站的好,天津建设工程信息网怎么报名的,加强文明网站建设,排名公式归并排序是一种分治算法#xff0c; 其思想是#xff1a; 将原始数组切分成较小的数组#xff0c;直到每个小数组只有一 个位置#xff0c;接着将小数组归并成较大的数组#xff0c;直到最后只有一个排序完毕的大数组 归并排序是第一个可以被实际使用的排序算法。它比前面… 归并排序是一种分治算法 其思想是 将原始数组切分成较小的数组直到每个小数组只有一 个位置接着将小数组归并成较大的数组直到最后只有一个排序完毕的大数组 归并排序是第一个可以被实际使用的排序算法。它比前面的几种排序方法效率要好很多 因为是分治思想所以要用到递归。
代码实现
//归并排序的特点
// 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;
}复杂度
时间复杂度O(nlogn)空间复杂度:O(n)稳定排序算法
测试 const demo mergeSortRecursion([1, 5, 3, 4, 2,10,12])console.log( ~ demo:, demo)一定要借助断点调试查看执行的流程不然实在无法理解这个实现过程大佬就自便了
