归并排序（Merge Sort）

介绍

归并排序是一个递归的算法，其基本思想是将一个待排序的数组分成两个小数组，分别对这两个小数组进行排序， 然后将这两个已排序的小数组合并成一个最终的已排序数组。若将两个有序表合并成一个有序表，称为二路归并。 归并排序的时间复杂度是O(n log n)，并且它是一个稳定的排序算法。

不是很优雅

0(n) 的空间复杂度，感觉不是特别优雅；

动画演示

工作原理

归并排序的工作原理主要分为分解和合并两个步骤：

• 分解： 将待排序的数组分割成两个子数组。如果数组的长度小于或等于1，则直接返回数组，因为它已经是排序的。否则，将数组从中间分割成两个子数组，并递归地对这两个子数组进行归并排序。
• 合并： 将两个已排序的子数组合并成一个已排序的数组。创建一个新的数组用于存储合并后的结果， 使用两个指针分别指向两个子数组的起始位置，比较两个指针指向的元素，将较小的元素放入新数组，并移动指针。 继续从两个子数组中取出较小的元素，直到其中一个子数组被完全处理。将未处理的另一个子数组中的剩余元素全部添加到新数组中。最后，将新数组的内容复制回原数组中。

算法特性

• 稳定性： 归并排序是稳定的排序算法，即相等的元素的顺序不会改变。这对于要排序数据包含多个信息而要按其中的某一个信息排序，要求其它信息尽量按输入的顺序排列时很重要。
• 时间复杂度： 归并排序的时间复杂度为O(n log n)，其中n是待排序元素的数量。这个复杂度在最好、最坏和平均情况下都是一致的。
• 空间复杂度： 归并排序需要额外的存储空间来存放合并后的序列，因此其空间复杂度为O(n)。
• 适用性： 归并排序适用于数据量大，并且对稳定性有要求的场景。此外，归并排序还可以作为其他高级排序算法的基础，如外部排序、多路归并排序等。

源码

<script setup lang="ts">
import SortBarChart from "../comp/sort-bar-chart.vue";
import { ref } from "vue";
import { genRandArray, sortExchangeReact } from "../sort.util";
import { sleep } from "../../../utils/cmm.util";

const data = ref<number[]>(genRandArray(1, 100, 100));
const data2 = ref<number[]>(new Array(100).fill(0));

const refreshData = () => {
  data.value = genRandArray(1, 100, 100);
  data2.value = new Array(100).fill(0);
};

const stepInterval = ref<number>(20);
const actives = ref<number[]>([]);

/**
 * 归并排序开始
 */
const sort = async () => {
  for (let len = 1; len < data.value.length; len *= 2) {
    for (let i = 0; i < data.value.length; i += len * 2) {
      let p1 = i;
      let p2 = i + len;
      for (let pr = i; pr < Math.min(i + len * 2, data.value.length); pr++) {
        await sleep(stepInterval.value);
        actives.value = [p1, p2];
        if (p1 >= i + len) data2.value[pr] = data.value[p2++];
        else if (p2 >= i + len * 2) data2.value[pr] = data.value[p1++];
        else {
          if (data.value[p1] > data.value[p2]) data2.value[pr] = data.value[p2++];
          else data2.value[pr] = data.value[p1++];
        }
      }
    }
    // 为了动画效果，将辅助数组的数据拷贝到原数组中
    data.value = data2.value;
    data2.value = new Array(100).fill(0);
  }
};
</script>

<template>
  <div class="">
    <a-space direction="horizontal">
      <a-input-number v-model="stepInterval" :step="50" :min="5" style="width: 200px">
        <template #suffix>ms</template>
        <template #prefix> 步进间隔</template>
      </a-input-number>
      <a-button @click="sort()">开始排序</a-button>
      <a-button @click="refreshData">刷新数据</a-button>
    </a-space>
    <div class="mt-sm" style="height: 300px">
      <sort-bar-chart :data="data" :actives="actives" />
    </div>

    <div class="mt-sm">辅助数组，临时存放归并后的数组</div>
    <div class="mt-sm" style="height: 300px">
      <sort-bar-chart :data="data2" />
    </div>
  </div>
</template>

<style scoped lang="less"></style>