js归并排序算法的原理及简单demo

最近看了一道“如何给阿里两万多名员工按照年龄排序”的面试题后,很想记录下来自己的解题思路,下面:
综合考虑到基数较大和稳定性,我们采取归并排序的算法;
归并算法分为两个两个灵魂步骤,即:拆分=>归并;
我们先把两万多名员工的基数缩小至六名员工的基数,他们的年龄数组未排序前为[25,18,17,31,25,30],我们实现第一个灵魂操作,拆分:
归并算法的拆分思想是将一个数组一分为二,然后将分出来的数组继续一分为二,直至出现单个数组的长度为1,不可再分为止;

js归并排序算法的原理及简单demo

如上图,一个长度为6的数组按照左右结构一直拆分至6个长度为1的数组,拆分就完毕了,这时我们由下往上回溯,将数组归并,图解:

js归并排序算法的原理及简单demo

六个长度为一的数组归并之后又变成了一个长度为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]))
控制台打印出结果:

js归并排序算法的原理及简单demo
这个时候我们可以看到,我们已经采用递归的方式将数组拆分为六个长度为一的数组了,接下来走第二步的合并,合并的思想是左右两个数组的第一个元素比较大小,然后将大的数(或者小的数)提取出来存放在一个第三方数组,直接上代码:

// 合并
            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]))//代码到这一步只是展示了合并的原理和思路,并不完整,我们不急,先用简单的单元素数组进行排序合并,这也是合并的第一层合并

js归并排序算法的原理及简单demo

控制台打印出[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]))

控住台打印:
js归并排序算法的原理及简单demo
至此,我们的归并排序成功!
欢迎各位大小神同行予以指正和探讨

相关推荐