归并排序是一种稳定排序,有必要掌握它;以下是详细代码加注释。先看一张归并排序算法对待排序数组的分割:
归并排序示意图" class="has" height="300" src="https://img-blog.csdnimg.cn/20190508214701975.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3OTU0NjQz,size_16,color_FFFFFF,t_70" width="274" />
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>归并排序</title>
</head>
<body>
<script type="text/javascript">
//归并排序:首先把数组分成两半,再分两半,一直到不可分,数组长度为1;
//接着调用merge函数,对左右数组排序,然后递归,最后实现整个数组的归并排序。
function mergeSort(arr) {
var len = arr.length;
if(len > 1) {
var index = Math.floor(len / 2);
console.log(index);
var left = arr.slice(0,index); //得到下标从0~index-1的数组
var right = arr.slice(index); //得到下标从index开始到末尾的数组
return merge(mergeSort(left) , mergeSort(right)); //里面采用递归
}else {
return arr;
}
}
function merge(left , right) {
//每次left或者right都是要shift掉第一个元素,表示left或者right是会变化的,最后arr.concat左右数组,
//因为不知道left或者right其中哪个数组剩下元素,简单做法,干脆将left和right数组都进行concat。
var arr = [];
while(left.length && right.length) {
if(left[0] < right[0]) {
arr.push(left.shift());
}else {
arr.push(right.shift());
}
}
//console.log(left+"——"+right);
//可以打印验证一下每次merge的时候,剩下的是left数组还是right数组里面的元素;加深对归并排序的理解
return arr.concat(left , right);
}
var arr=[4,19,60,10,66];
console.log('beforeSort:'+arr);
mergeSort(arr);
console.log('afterSort:'+arr);
</script>
</body>
</html>
浏览器F12控制台打印结果: