归并排序，递归深入学习（二叉树排序，了解二叉树！）
- 分析归并排序之前，先回顾一下冒泡排序。
最开始梳理的冒泡排序的时候除了一个大问题，我想的是把arr[0] 跟每一个后面的数字进行比较，如果进行位置的转换。出现的代码就变成如下代码。
function bubbleSort(arr){
for(var i=0; i<arr.length; i++){
for(var n=0; n<arr.length; n++){
if(arr[i] > arr[n]){
arr[i] ^= arr[n];
arr[n] ^= arr[i];
arr[i] ^= arr[n];
}
}
}
return arr;
}
a[i] --> 是获取最外层循环的第一个数据，然后跟内层的第二个开始比较，如果内层循环的数据小于外层的数据那么交换位置。 这种方式是每一个进行对比后交换位置，计算下来循环俩是整整的两倍！不像传说中的冒泡啊！
这特么是传统的排序方法啊，要浪费好多时间。。
立马去百度了一下冒泡排序图解。
1.png
2.png
3.png
4.png
oh my god ！！！错了吧，思想跑歪了。
理解上面的图解然，重新整理冒泡排序代码！
function subbleSort(arr){
for(var i=0; i<arr.length; i++){
for(var n=0; n<arr.length-i-1; n++){
if(arr[n] > arr[n+1]){
arr[n] ^= arr[n+1];
arr[n+1] ^= arr[n];
arr[n] ^= arr[n+1];
//es6 结构赋值 [ arr[n],arr[n+1] ] = [ arr[n+1], arr[n] ];
}
}
}
return arr;
}
通过冒泡排序得是想完成了代码，发现内层循环不会像第一个传统排序那么臃肿复杂了！
若果用node的startime 和 endtime 能看到节约了很多计算时间。
-
归并排序 及二叉树排序
归并排序分析数图，用什么方来对他进行排序。要了解二叉树结构。
递归.png
归并分析后代码书写
//分析二叉树图，然后我们要分左边右边，两边的数据 例如 3 1 2 -> Math.floor(arr.length/2);
function merge(left,right){
var result = [];
//循环左右两边的数据
while(left.length && right.length){
//如果右边第一个小于左边第一个将右边的第一个截取出来放入新的数组 否则 左边的取出
if(left[0] <= right[0]){
result.push(left.shift());
}else{
result.push(right.shift());
}
}
//经过上面的循环后 其中一遍没有数据。
while(left.length){ //如果右边还有数据就将右边取出
result.push(left.shift());
}
while(right.length){ //如果左边还有数据将左边取出 在这种情况下只有左边有Math.floor
result.push(right.shift());
}
return result; //返回
}
//注： 可以将 [ 3, 1, 2 ]带入其中
//主函数
function mergeSort(arr){
//设置递归结束条件
if(arr.length < 2){
return arr; // 当数组长度只有1的时候 直接返回这个就好了
}
//设置数组的中间值 [3,1,2] 要将他分成左边和右边的树
var mid = Math.floor(arr.length/2);
var left = arr.slice(0,mid);
var right = arr.slice(mid);
return merge(mergeSort(left),mergeSort(right));
}
//加密是碰见要求无限层数组对象排序，递归
function sortObjKey(obj) {
let newObj = {};
Object.keys(obj).sort().forEach(item => {
if (typeof obj[item] === 'object') {
if (Array.isArray(obj[item])) {
obj[item].forEach(it => {
it = sortObjKey(it);
})
} else {
obj[item] = sortObjKey(obj[item]);
}
}
newObj[item] = obj[item];
})
return newObj
}
console.log(sortObjKey(obj),'???');
