数据结构和算法之归并排序

归并排序（Merge Sort）是一种基于分治思想的排序算法，通过将待排序的数组分成两个子数组，分别对两个子数组进行排序，最后将排序好的子数组合并成一个有序数组。它的基本思想是将两个有序的子序列合并成一个有序的序列。

代码如下：

// 归并排序算法
function mergeSort(arr) {
  // 递归出口，当数组长度小于等于1时，直接返回数组本身
  if (arr.length <= 1) {
    return arr;
  }

  // 找到数组的中间位置，将数组分成两个子数组
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  // 递归对左右两个子数组进行排序
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);

  // 合并两个有序的子数组
  return merge(sortedLeft, sortedRight);
}

// 合并两个有序的子数组
function merge(left, right) {
  const merged = [];
  let i = 0; // 左子数组指针
  let j = 0; // 右子数组指针

  // 比较左右子数组的元素，将较小的元素依次放入合并后的数组中
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      merged.push(left[i]);
      i++;
    } else {
      merged.push(right[j]);
      j++;
    }
  }

  // 将剩余的元素放入合并后的数组中
  while (i < left.length) {
    merged.push(left[i]);
    i++;
  }
  while (j < right.length) {
    merged.push(right[j]);
    j++;
  }

  return merged;
}

// 测试
const arr = [4, 2, 7, 5, 1, 6, 3, 8];
const sortedArr = mergeSort(arr);
console.log(sortedArr); // 输出 [1, 2, 3, 4, 5, 6, 7, 8]
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
44
45
46
47
48
49
50
51
52
53
54

算法步骤如下：

1. 归并排序算法通过递归对一个待排序数组进行排序。
2. 在每一层递归中，将数组一分为二，分别得到左右两个子数组。
3. 继续递归调用归并排序算法，分别对左右两个子数组进行排序。
4. 当子数组长度小于等于1时，递归出口，直接返回该子数组本身。
5. 将两个有序的子数组合并成一个有序的数组。
6. 合并过程中，使用两个指针分别指向左右两个子数组的元素，比较两个元素的大小，选择较小的元素放入合并后的数组，直到遍历完左右两个子数组。
7. 将剩余的元素依次放入合并后的数组中。
8. 返回合并后的数组作为结果。

下面是归并排序算法的流程图表示：

               [4,2,7,5,1,6,3,8]
             /                 \
      [4,2,7,5]              [1,6,3,8] 
       /     \                /     \
    [4,2]   [7,5]           [1,6]  [3,8] 
   /    \     /   \        /    \    /    \
 [4]   [2]   [7]   [5]    [1]  [6]  [3]  [8] 
   \    /     \   /        \    /    \    /
    [2,4]    [5,7]         [1,6]    [3,8] 
       \      /    \         /       \       
    [2,4,5,7]    [1,3,6,8]            
           \       /   
      [1,2,3,4,5,6,7,8]
1
2
3
4
5
6
7
8
9
10
11
12
13

在这个流程图中，每一层递归都将数组分成两部分，最后合并成一个有序的数组。