摘要：最近看了一道如何给阿里两万多名员工按照年龄排序的面试题后，很想记录下来自己的解题思路，下面综合考虑到基数较大和稳定性，我们采取归并排序的算法归并算法分为两个两个灵魂步骤，即拆分归并我们先把两万多名员工的基数缩小至六名员工的基数，他们的年龄数
最近看了一道“如何给阿里两万多名员工按照年龄排序”的面试题后，很想记录下来自己的解题思路，下面：
综合考虑到基数较大和稳定性，我们采取归并排序的算法；
归并算法分为两个两个灵魂步骤，即：拆分=>归并；
我们先把两万多名员工的基数缩小至六名员工的基数，他们的年龄数组未排序前为[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]))
控住台打印：
至此，我们的归并排序成功！
欢迎各位大小神同行予以指正和探讨
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/104068.html
摘要：下面会介绍的一种排序算法快速排序甚至被誉为世纪科学和工程领域的十大算法之一。我们将讨论比较排序算法的理论基础并中借若干排序算法和优先队列的应用。为了展示初级排序算法性质的价值，我们来看一下基于插入排序的快速的排序算法希尔排序。 前言 排序就是将一组对象按照某种逻辑顺序重新排列的过程。比如信用卡账单中的交易是按照日期排序的——这种排序很可能使用了某种排序算法。在计算时代早期，大家普遍...
摘要：栈被称为一种后入先出的数据结构。散列使用的数据结构叫做散列表。这些操作需要求助于其他数据结构，比如下面介绍的二叉查找树。 前言 在过去的几年中，得益于Node.js的兴起，JavaScript越来越广泛地用于服务器端编程。鉴于JavaScript语言已经走出了浏览器，程序员发现他们需要更多传统语言（比如C++和Java）提供的工具。这些工具包括传统的数据结构（如链表，栈，队列，图等），...
摘要：本篇主要实现九八大排序算法，分别是冒泡排序，插入排序，选择排序，希尔排序，归并排序，快速排序，堆排序计数排序。希尔排序是非稳定排序算法。归并排序算法依赖归并操作。但是，计数排序可以用在基数排序算法中，能够更有效的排序数据范围很大的数组。 本篇主要实现九(八）大排序算法，分别是冒泡排序，插入排序，选择排序，希尔排序，归并排序，快速排序，堆排序,计数排序。希望大家回顾知识的时候也能从我的这...
阅读 754·2021-11-09 09:47
阅读 1529·2019-08-30 15:44
阅读 1123·2019-08-26 13:46
阅读 2086·2019-08-26 13:41
阅读 1241·2019-08-26 13:32
阅读 3728·2019-08-26 10:35
阅读 3498·2019-08-23 17:16
阅读 418·2019-08-23 17:07
