前端实现归并排序的思路

function mergeSort(arr) {  
  if (arr.length <= 1) {  
    return arr;  
  }  
    
  const mid = Math.floor(arr.length / 2);  
  const left = arr.slice(0, mid);  
  const right = arr.slice(mid);  
    
  return merge(mergeSort(left), mergeSort(right));  
}  
  
function merge(left, right) {  
  const result = [];  
  let i = 0;  
  let j = 0;  
    
  while (i < left.length && j < right.length) {  
    if (left[i] <= right[j]) {  
      result.push(left[i]);  
      i++;  
    } else {  
      result.push(right[j]);  
      j++;  
    }  
  }  
    
  return [...result, ...left.slice(i), ...right.slice(j)];  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

几个想法说明下：
1 关于merge(mergeSort(left), mergeSort(right));的想法由来
2 [...result, ...left.slice(i), ...right.slice(j)];ES6用法的使用

1 关于merge(mergeSort(left), mergeSort(right));的推导
归并排序，基本查查资料都知道采用的是分治的思想。两个关键点：分和归
实现的思路整体上是这样的：把一个数组分成两个数组（假设这两个数组已经有序了，这里很关键，如果不是有序的，你还要在分，这里就是递归的思想），然后进行归，也就是合并。但是怎么合并呢？很多人查看资料，也知道是通过遍历比对。我们先不管那么多，假设我们有个函数merge，实现合并的。敲黑板！！重点来了。我们从分解到合并的过程，考虑简单点，假设分解后，我们的两个数组都是有序的，我们就能合并了。所以我们合并的就是原数组的两个分支，merge(left,right)，这里left,right就是分解后的有序数组。那么在思考下，如果left和right不是有序的呢？是不是还要在分，然后合？所以我们最后合并的是left和right分到最后一层后的合。即merge(mergeSort(left),mergeSort(right))

这里我在演绎下推到过程：
递归有几个步骤：找到递推体，找到退出条件。
我们高中学的f(n)=f(n-1)+1就是一种递归
1 找到递归体

//首先我们写一个函数，这个函数就是把数组分开，然后合并的
function mergeSort(arr){
	//把数组分成两个left/right进行合并
	const mid = Math.floor(arr.length / 2);  
    const left = arr.slice(0, mid);  
    const right = arr.slice(mid);
    return merge(left,right)
}
//但是上面的有个前提，就是left/right都是有序的，要是无序的怎么办？继续自调用分
function mergeSort(arr){
	//把数组分成两个left/right进行合并
	const mid = Math.floor(arr.length / 2);  
    const left = arr.slice(0, mid);  
    const right = arr.slice(mid);
    return merge(mergeSort(left),mergeSort(right))
}
//那怎么合并呢？通过指针逐次比对两个数组的大小
function merge(left,right){
  const result = [];  
  let i = 0;  
  let j = 0;  
    
  while (i < left.length && j < right.length) {  
    if (left[i] <= right[j]) {  
      result.push(left[i]);  
      i++;  
    } else {  
      result.push(right[j]);  
      j++;  
    }  
  }  
    
  return [...result, ...left.slice(i), ...right.slice(j)]; 
}
//当什么时候不需要在分呢？有序或者只有1个数的时候
function mergeSort(arr){
	if(arr.length<2) return arr;
	//把数组分成两个left/right进行合并
	const mid = Math.floor(arr.length / 2);  
    const left = arr.slice(0, mid);  
    const right = arr.slice(mid);
    return merge(left,right)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43