JavaScript实现归并排序算法

归并排序稍微复杂一丢丢&＃xff0c;但是它的性能比前面的冒泡、选择和插入排序都好一点&＃xff0c;是可以用在实战中的排序算法&＃xff0c;听说以前火狐浏览器就是用它的

归并排序算法动图

一、归并排序的算法思路

底下的过程也不知道有没有说清楚&＃xff0c;我总结一下就是&＃xff0c;每每劈成两半&＃xff0c;分成大组&＃xff0c;大组里面分小组&＃xff0c;一直二分&＃xff0c;分到一个一组&＃xff0c;不能分了&＃xff0c;就是套娃
然后再从左边开始&＃xff0c;从最小的组开始两两比较大小&＃xff0c;左边两个比一下&＃xff0c;右边两个比一下&＃xff0c;再这四个比一下&＃xff0c;再往外扩大范围用这个方式去比~

之前的过程说明

为了说清楚&＃xff0c;假如有10个数

1、分组

先分组&＃xff0c;大组分小组&＃xff0c;再分小小组&＃xff0c;直到分成一个数一组
左边是L&＃xff0c;右边是R&＃xff0c;每一个-表示后面的细分小组
&＃xff08;1&＃xff09;归并排序就是先对半劈&＃xff0c;分成左边L1组5个和右边R2组5个两组
&＃xff08;2&＃xff09;左边5个分成左左边L1-L1组3个和右右边L1-R1组2个两组
&＃xff08;3&＃xff09;左左边的3个分成左左左边L1-L1-L1组的2个和右右右边L1-R1-L1组的1个
&＃xff08;4&＃xff09;左左左边的2个分成左左左左边L1-L1-L1-L1组的1个和右右右右边L1-L1-L1-R1组的1个
&＃xff08;5&＃xff09;前面的右边也要分直到分成1个和1个&＃xff0c;省略不写了
这个要结合前面那个网址的动图来看~

2、排序

&＃xff08;1&＃xff09;左左左左边L1-L1-L1-L1组的1个数和右右右右边L1-L1-L1-R1组的1个数&＃xff0c;来排序
小的一个就站出来&＃xff0c;站到前面&＃xff0c;另一个排到它后面&＃xff0c;再回到队列里
&＃xff08;2&＃xff09;L1-L1-R1-L1组的1个数和右右右右边L1-L1-R1-R1的一个数比较
&＃xff08;3&＃xff09;这样的话&＃xff0c;L1-L1的左边和L1-L1的右边就排好了是不是&＃xff0c;再把
L1-L1-L1组的和L1-L1-R1的排列一下
啊啊啊~我好累。。。。。还是看图吧&＃xff0c;不写了

二、编码实现

根据一的算法思路很明显的发现
第一需要递归不断的对半分
第二需要一个队列排序&＃xff0c;每次小组排序时&＃xff0c;把小的拿出来放在队列头

Array.prototype.mergeSort &＃61; function() {const rec &＃61; (arr) &＃61;> {const len &＃61; arr.length;// 已经分到1个1组&＃xff0c;不能再分啦if(len &＃61;&＃61;&＃61; 1) return arr;const mid &＃61; Math.floor(len/2);const leftArr &＃61; arr.slice(0, mid);const rightArr &＃61; arr.slice(mid, len);// 来递归分组啦// 这两个看做队列const leftOrder &＃61; rec(leftArr);const rightOrder &＃61; rec(rightArr);// 结果数组const res &＃61; [];// 分好组就来小组排序while(leftOrder.length || rightOrder.length) {if(leftOrder.length && rightOrder.length) {// 比较队列头&＃xff0c;小的就shift出来push到res里res.push(leftOrder[0] < rightOrder[0] ? leftOrder.shift(0) : rightOrder.shift(0));} else if(leftOrder.length) {res.push(leftOrder.shift(0));} else if(rightOrder.length) {res.push(rightOrder.shift(0));} else {break;}}return res;}const res &＃61; rec(this);// 将res赋值到this也就是传进来的数组本身上res.forEach((item, key) &＃61;> {this[key] &＃61; item;})
}const arr &＃61; [1, 5, 9, 3, 18, 6, 2, 7, 0, 6]
arr.mergeSort()
console.log(arr);


三、算法时间复杂度

1、两两分组&＃xff0c;用上递归&＃xff0c;这种时间复杂度一般都是O(logn)
2、排序&＃xff0c;也就是递归里面有个while循环&＃xff0c;看到了吧&＃xff0c;这种就是O(n)
所以这个排序算法的时间复杂度是O(nlogn)

终于写完了&＃xff0c;写完发现也不是很难~算法还是以理解为主吧