js合并排序算法的道理及简朴demo

近来看了一道“怎样给阿里两万多名员工根据岁数排序”的面试题后，很想记录下来本身的解题思绪，下面：
综合考虑到基数较大和稳定性，我们采纳兼并排序的算法；
兼并算法分为两个两个魂魄步骤，即：拆分=>兼并；
我们先把两万多名员工的基数缩小至六名员工的基数，他们的岁数数组未排序前为[25,18,17,31,25,30],我们完成第一个魂魄操纵，拆分:
兼并算法的拆分头脑是将一个数组一分为二，然后将分出来的数组继承一分为二，直至涌现单个数组的长度为1，不可再分为止；

如上图，一个长度为6的数组根据摆布构造一向拆分至6个长度为1的数组，拆分就终了了，这时刻我们由下往上回溯，将数组兼并，图解：

六个长度为一的数组兼并之后又变成了一个长度为6的数组，然则排序发生了转变，这就是兼并算法，下面是代码完成：

我们一步一步来，第一步先来完成拆分的部份：

// 拆分
function mergeSort(arr){
console.log(`arr=${arr}`)
if(arr.length==1){//假如数组长度为1则返回数组
return arr
}
var mid=Math.floor(arr.length/2);//将数组一拆分为二
var left=arr.slice(0,mid);
var right=arr.slice(mid);
mergeSort(left);//假如数组长度不为1，则继承递归拆分，（由控制台可以看出递归会先将left实行完后再去实行right）
mergeSort(right)
}
console.log(mergeSort([25,18,17,31,25,30]))

控制台打印出效果：


这个时刻我们可以看到，我们已采纳递归的体式格局将数组拆分为六个长度为一的数组了，接下来走第二步的兼并，兼并的头脑是摆布两个数组的第一个元素比较大小，然后将大的数（或许小的数）提取出来存放在一个第三方数组，直接上代码：

// 兼并
function merge(left,right){
var arr=new Array;//新建一个第三方数组
if(left[0]<=right[0]){//比较left的第一位和right的第一位谁小，小的提取出来push进第三方数组
arr.push(left.shift())
}else{
arr.push(right.shift())
}
return arr.concat(left).concat(right)//将提取出来的数组和原数组兼并成一个数组
};
console.log(merge([25],[30]))//代码到这一步只是展现了兼并的道理和思绪，并不完全，我们不急，先用简朴的单位素数组举行排序兼并，这也是兼并的第一层兼并

控制台打印出[25,30],申明我们的兼并和排序都是胜利的，下面我们将晋级两个函数，使其可以正式地操纵庞杂的兼并排序：

// 兼并
function merge(left,right){
var arr=new Array;//新建一个第三方数组
while(left.length>0&&right.length>0){////比较left的第一位和right的第一位谁小，小的提取出来push进第三方数组
if(left[0]<=right[0]){
arr.push(left.shift())
}else{
arr.push(right.shift())
}
};
return arr.concat(left).concat(right)//将提取出来的数组和原数组兼并成一个数组
};
// 拆分
function mergeSort(arr){
console.log(`arr=${arr}`)
if(arr.length==1){//假如数组长度为1则返回数组
return arr
};
var mid=Math.floor(arr.length/2);//将数组一拆分为二
var left=arr.slice(0,mid);
var right=arr.slice(mid);
return merge(mergeSort(left),mergeSort(right))
};
console.log(mergeSort([25,18,17,31,25,30]))

控住台打印：

至此，我们的兼并排序胜利！
迎接列位大小神偕行予以指正和讨论