TypeScript实现十大排序算法之归并排序示例详解

简介

本文将详细介绍使用 TypeScript 实现归并排序算法的步骤和示例。归并排序是一种非常有效的排序算法，它的时间复杂度为 O(nlogn)，在大多数情况下都比快速排序更加稳定和可靠。

步骤

归并排序是一种典型的分治算法，其基本思路是将待排序的数组不断分割为较小的数组，直到每个小数组只有一个元素，然后将这些小数组两两合并，直到得到一个有序的大数组。具体步骤如下：

1. 将待排序的数组分成两个子数组，每个子数组包含大约一半的元素。
2. 对每个子数组进行归并排序，这是一个递归过程。
3. 将两个排好序的子数组合并成一个有序的大数组。合并时需要分别比较两个子数组的第一个元素，较小的插入到结果数组中。如果一个子数组的元素已经全部插入结果数组中，那么另一个子数组中剩余的元素可以直接插入于结果数组中。

代码示例

下面是使用 TypeScript 实现归并排序的示例代码：

function mergeSort(arr: number[]): number[] {
  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);
  // 将排序后的子数组合并成一个有序的大数组
  const merged: number[] = [];
  let i = 0;
  let j = 0;
  while (i < sortedLeft.length && j < sortedRight.length) {
    if (sortedLeft[i] < sortedRight[j]) {
      merged.push(sortedLeft[i]);
      i++;
    } else {
      merged.push(sortedRight[j]);
      j++;
    }
  }
  return merged.concat(sortedLeft.slice(i)).concat(sortedRight.slice(j));
}

const arr = [6, 5, 3, 1, 8, 7, 2, 4];
const sortedArr = mergeSort(arr);
console.log(sortedArr);

上面的代码中，首先判断数组是否只包含一个元素，如果是则返回该数组；否则，将数组分割成两个子数组并对它们进行递归地归并排序。最终，将排序后的子数组合并成一个有序的大数组并返回。

示例说明

下面是两个使用示例：

示例 1

const arr = [6, 5, 3, 1, 8, 7, 2, 4];
const sortedArr = mergeSort(arr);
console.log(sortedArr);

这个示例调用了上述的 mergeSort 函数，对数组 [6, 5, 3, 1, 8, 7, 2, 4] 进行归并排序。函数的返回值是一个排好序的新数组 [1, 2, 3, 4, 5, 6, 7, 8]。可以通过打印输出结果来验证排序的正确性。

示例 2

const arr = [2, 4, 6, 8, 10, 9, 7, 5, 3, 1];
const sortedArr = mergeSort(arr);
console.log(sortedArr);

这个示例对一个已经排好序的数组 [2, 4, 6, 8, 10, 9, 7, 5, 3, 1] 进行归并排序。虽然数组已经排好序，但是这并不会影响归并排序的正确性。输出结果是一个排好序的新数组 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]。