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

作者：函数茶馆时间：2026-10-27 01:38:32浏览：195

本文详解TypeScript中归并排序的实现。归并排序基于分治思想，通过递归分解数组并合并有序子数组，实现O(nlogn)的高效排序。文章提供完整TS代码、图解流程及最好、最坏、平均时间复杂度分析，帮助开发者掌握这一经典稳定排序算法。

一. 归并排序的定义

归并排序（merge sort）是一种广泛应用的排序算法。

其核心策略是将待排序数组划分为多个子数组。
接着，将相邻的子数组两两归并，形成更大的有序数组。
最终，所有有序子数组被归并（merge）为一个完整的有序数组。

该算法最早由约翰·冯·诺伊曼（John von Neumann）于1945年提出。作为现代计算机之父，他提出了冯·诺依曼结构和普林斯顿结构。

当时他受雇于美国政府，致力于原子弹相关问题的研究。
鉴于当时计算机硬件的限制，他在研究中提出了一种高效的计算方法，即归并排序。

归并排序的基本思路是：首先递归地将待排序数组拆分为两个子数组，然后对每个子数组分别进行排序，最后将两个有序子数组合并成一个有序数组。

在实现层面，我们可以采用“分治法”来完成这一过程，即将大问题分解为小问题逐一解决。

归并排序的算法复杂度为 O(nlogn)，属于较为高效的排序算法，因此在实际应用中非常广泛。

尽管归并排序看似复杂，但只要理解其基本思路，实现起来并不困难，且该算法本身颇具趣味性。

二. 归并排序的流程

归并排序是一种基于分治思想的排序算法，其基本思路可概括为三个步骤：

步骤一：分解（Divide）：归并排序利用递归算法实现分解过程，具体实现包含以下步骤：

若待排序数组长度为1，则视为已有序，直接返回；
将待排序数组划分为两个长度大致相等的子数组，并分别对这两个子数组进行递归排序；
将两个已排序的子数组合并成一个有序数组，并返回该结果。

步骤二：合并（Merge）：在合并过程中，需比较各子数组的元素，并将它们有序地合并为新数组：

可使用两个指针 i 和 j 分别指向两个子数组的起始位置，比较元素大小，将较小者插入新的有序数组中。
若其中一个子数组已遍历完毕，则将另一个子数组的剩余部分直接追加到新有序数组中。
最后返回合并后的有序数组。

步骤三：归并排序的递归终止条件：

归并排序采用递归算法进行分解，当子数组长度减至1时，认为该子数组已有序，递归结束。

总体而言，归并排序的基本思路是分治法，即分解子问题分别解决，再将子问题的解合并为整体解。

三. 归并排序的图解

一. 归并排序的定义

四. 归并排序的代码

以下是使用TypeScript实现的归并排序代码，附带详细注释：

// 定义函数mergeSort，参数是待排序数组arr
function mergeSort(arr: number[]): number[] {
    // 计算数组长度
    const n = arr.length;
    // 如果数组长度小于等于1，则直接返回该数组
    if (n <= 1) {
        return arr;
    }
    // 计算中间位置
    const middle = Math.floor(n / 2);
    // 对左边的数组进行归并排序
    const left = mergeSort(arr.slice(0, middle));
    // 对右边的数组进行归并排序
    const right = mergeSort(arr.slice(middle));
    // 合并两个排好序的数组
    return merge(left, right);
}

// 定义函数merge，参数是两个排好序的数组left和right
function merge(left: number[], right: number[]): number[] {
    // 定义指针变量，分别指向两个数组的开头
    let i = 0, j = 0;
    // 定义一个空数组，用来存放合并后的数组
    const result = [];
    // 比较两个数组的第一个元素，将较小的放入result数组
    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }
    // 将没有比较完的剩余元素放入result数组
    while (i < left.length) {
        result.push(left[i++]);
    }
    while (j < right.length) {
        result.push(right[j++]);
    }
    // 返回合并后的数组
    return result;
}


// 测试数据
const testArr = [5, 2, 9, 1, 5, 6];
// 调用插入排序函数
const sortedArr = mergeSort(testArr);
// 打印结果
console.log(sortedArr);

代码执行流程如下：