排序算法-归并排序

归并排序

前面我们已经介绍讲解了冒泡排序、选择排序、拆入排序、快速排序了，本文主要讲解归并排序，如果有写的错误的地方还望大家能指出。

归并排序介绍

归并排序采取的是分治思想。
分治：分而治之，将大的问题分解成小的子问题来解决，小的子问题都解决了，大的问题也就解决了。
用图来表示能更加清楚：

看完以上图我们可以得出，将无序的数组通过归并进行排序主要有以下两个步骤：拆分成最小子序列，合并排序最小的子序列。

拆分

/**
 * @description: 归并排序-拆分
 * @param {Array} 待拆分的数组
 */

function sortArray(arr) {
    const length = arr.length;
    if (length === 1) { //递归算法的停止条件，即为判断数组长度是否为1
        return arr;
    }
    const mid = Math.floor(length / 2);
   
    const left = arr.slice(0,  mid);
    const right = arr.slice(mid, length);
  
    return merge(sortArray(left), sortArray(right)); //要将原始数组分割直至只有一个元素时，才开始归并
}

sortArray([38, 27, 43, 3, 9, 82, 10])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

排序

将两个已排好序的数组合并成一个有序的数组,称之为归并排序的合并
步骤：创建一个空的合并数组，遍历两个数组，比较它们的值。谁比较小，谁先放入合并的数组中，直到数组遍历完成。

例如：
[38] [27] 合并为有序数组：[27, 38]；
[48] [3] 合并为有序数组: [3, 48]
[27, 38] [3, 48] 两有序数组合并为一个有序数组，

• 1. 拿出arr1[0]和arr2[0]进行比较，显然是arr2[0]比较小，因此将arr2[0]放入结果数组中，同时arr2指针往后一格。 27 < 3, result = [3]
• 2. 随后，拿arr1[0]和arr2[1]进行比较，显然是arr1[0]比较小，将arr1[0]放入结果数组中，同时arr1指针往后一格。 27 < 48, result = [3, 27]
• 3. 随后，拿arr1[1]和arr2[1]进行比较，显然是arr2[1]比较小，将arr2[1]放入结果数组中，同时arr2指针往后一格。 38 < 48, result = [3, 27, 38]
• 4. 剩下的一个arr1[1]，直接加入结果数组中。 [3, 27, 38, 48]

function merge(left, right) {
   const result = [];
   let il = 0;
   let ir = 0;

   //left, right本身肯定都是从小到大排好序的
   while( il < left.length && ir < right.length) {
       if (left[il] < right[ir]) {
           result.push(left[il]);
           il++;
       } else {
           result.push(right[ir]);
           ir++;
       }
       
   }

   //不可能同时存在left和right都有剩余项的情况, 要么left要么right有剩余项, 把剩余项加进来即可
   while (il < left.length) { 
       result.push(left[il]);
       il++;
   }
   while(ir < right.length) {
       result.push(right[ir]);
       ir++;
   }
   return result;
}
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

最终代码

function sortArray(arr) {
   const length = arr.length;
   if (length === 1) { //递归算法的停止条件，即为判断数组长度是否为1
       return arr;
   }
   const mid = Math.floor(length / 2);
  
   const left = arr.slice(0,  mid);
   const right = arr.slice(mid, length);
 
   return merge(sortArray(left), sortArray(right)); //要将原始数组分割直至只有一个元素时，才开始归并
}

function merge(left, right) {
   const result = [];
   let il = 0;
   let ir = 0;

   //left, right本身肯定都是从小到大排好序的
   while( il < left.length && ir < right.length) {
       if (left[il] < right[ir]) {
           result.push(left[il]);
           il++;
       } else {
           result.push(right[ir]);
           ir++;
       }
       
   }

   //不可能同时存在left和right都有剩余项的情况, 要么left要么right有剩余项, 把剩余项加进来即可
   while (il < left.length) { 
       result.push(left[il]);
       il++;
   }
   while(ir < right.length) {
       result.push(right[ir]);
       ir++;
   }
   return result;
}

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