在开始说之前先扯些面试中常见考察理解和分析问题的题目：
下面我们就来看该如何去选择算法，详见下图：
这里面来讲讲什么是稳定性
稳定性不能影响原来的顺序，比如说现在有三个员工和各自的年龄
1：55 2：55 3：40
现在按年龄排序
3：40 1：55 2：55 稳定
3：40 2：55 1：55 不稳定（影响了原来的顺序）
下面再来看看如何选择排序方法
考虑到稳定性，所以就选择归并排序
归并排序的实现原理：拆分=>归并
拆分：
比如数组[1,5,6,2,4,3]，归并排序的第一步，将数组一分为二：[1,5,6] [2,4,3] 接着将分成的数组继续一分为二，直到长度为1，构成如下二叉树：
归并：
当递归到了尽头，向上回溯，对于两个有序的数组，我们将它们合并成一个有序数组，完成整个归并排序（从下往上）
下面来看代码：
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Document</title> </head> <body> <script type="text/javascript"> //归并 function merge(left, right){ var result = [];//作为中间容器，临时存放 if(left[0] < right[0]){ result.push(left.shift()); }else{ result.push(right.shift()); } return result.concat(left).concat(right); } //拆分 function mergeSort(arr){ var mid = arr.length / 2; var left_arr = arr.slice(0, mid); var right_arr = arr.slice(mid); // console.log(left_arr); // console.log(right_arr); return merge(left_arr, right_arr); } var arr = [6,4]; console.log(mergeSort(arr)); </script> </body> </html>
代码两步走，先拆分再归并
输出结果：
但是当数组的长度加长的时候就会出现问题：
var arr = [6,4,7];
此时浏览器的结果：
这显然不是我们要的结果，这时候我们还要再加入拆分和判断，代码如图：
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Document</title> </head> <body> <script type="text/javascript"> //归并 function merge(left, right){ var result = [];//作为中间容器，临时存放 while(left.length > 0 && right.length > 0){ if(left[0] < right[0]){ result.push(left.shift()); }else{ result.push(right.shift()); } } return result.concat(left).concat(right); } //拆分 function mergeSort(arr){ if(arr.length == 1){ return arr; } var mid = arr.length / 2; var left_arr = arr.slice(0, mid); var right_arr = arr.slice(mid); // console.log(left_arr); // console.log(right_arr); return merge(mergeSort(left_arr), mergeSort(right_arr)); } var arr = [6,4]; console.log(mergeSort(arr)); </script> </body> </html>
这个时候就实现了排序，给数组加入一些数据测试一下：
var arr = [6,4,7,3,7,3,2,6];
结果：
原文：https://www.cnblogs.com/mataoblogs/p/10713954.html