大前端

4.1.8 归并排序 (稳定排序)

  • 时间复杂度：O(n log n)
  • 空间复杂度： O(n)

思路：分治策略，先进行划分，然后再进行合并。
假设要对数组C进行归并排序，步骤是：
1.先将C划分为两个数组A和B（即把数组C从中间分开）
2.再分别对数组A、B重复步骤1的操作，逐步划分，直到不能再划分为止(每个子数组只剩下一个元素)，这样，划分的过程就结束了。

如：              [12 20 30 21 15 33 26 19 40 25]
划分为:  [12 20 30 21 15]                [33 26 19 40 25]
           [12 20]      [30 21 15]       [33 26]       [19 40 25]
         [12]  [20]   [30]  [21 15]     [33]  [26]    [19]    [40 25]
         [12]  [20]   [30] [21] [15]    [33]  [26]    [19]   [40] [25]
1
2
3
4
5
6

3.然后从下层往上层不断合并数组，每一层合并相邻的两个子数组，
合并的过程是每次从待合并的两个子数组中选取一个最小的元素，
然后把这个元素放到合并后的数组中，不断重复直到把两个子数组的元素都放到合并后的数组为止。

4.依次类推，直到合并到最上层结束，这时数据的排序已经完成了

function merge(left, right) {
    let 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};
		let mid=Math.floor(arr.length/2);
		let left_arr = arr.slice(0,mid);
    let right_arr = arr.slice(mid);
    
		return merge(mergeSort(left_arr),mergeSort(right_arr));
	}
 
let arr = [12,20,30,21,15,33,26,19,40,25];
mergeSort(arr);
// [12, 15, 19, 20, 21, 25, 26, 30, 33, 40]
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

参考

← 4.1.9 二分查找 →