思想
这是一种分治算法。将原始数组切分成较小的数组,直到每个小数组只有一项,然后在将小数组归并为排好序的较大数组,直到最后得到一个排好序的最大数组。如下图 图片:save.jpg 视频说明:https://www.bilibili.com/video/av88058418?from=search&seid=12615007212925523963 js代码实现: function mergeSort(arr) { const length = arr.length; if (length === 1) { //递归算法的停止条件,即为判断数组长度是否为1 return arr; } const mid = Math.floor(length / 2); const left = arr.slice(0, mid); const right = arr.slice(mid, length); return merge(mergeSort(left), mergeSort(right)); //要将原始数组分割直至只有一个元素时,才开始归并 } function merge(left, right) { const result = []; let il = 0; let ir = 0; //left, right本身肯定都是从小到大排好序的 while( il < left.length && ir < right.length) { if (left[il] < right[ir]) { result.push(left[il]); il++; } else { result.push(right[ir]); ir++; } } //不可能同时存在left和right都有剩余项的情况, 要么left要么right有剩余项, 把剩余项加进来即可 while (il < left.length) { result.push(left[il]); il++; } while(ir < right.length) { result.push(right[ir]); ir++; } return result; } 代码参考:https://www.cnblogs.com/Bonnie3449/p/9574635.html 图片来自:https://segmentfault.com/a/1190000015488807 |
|
最新喜欢:LiWang |