归并排序（Merge Sort）

举报
林太白 发表于 2025/11/12 17:10:33 2025/11/12
【摘要】 归并排序（Merge Sort）

归并排序（Merge Sort）

认识

归并排序（Merge Sort）是一种基于分治法（Divide and Conquer）的高效排序算法。它将数组分成两半，分别对两半进行排序，然后将排序好的两半合并成一个有序数组。归并排序是稳定排序算法，时间复杂度为O(n log n)。

大致实现如下

function mergeSort(arr) {
    if(arr.length === 1) return arr
    
    let mid = Math.floor(arr.length / 2)
    let left = arr.slice(0, mid)
    let right = arr.slice(mid)
    
    return merge(mergeSort(left), mergeSort(right))
}

function merge(a, b) {
    let res = []
    
    while (a.length && b.length) {
        if (a[0] < b[0]) {
            res.push(a[0])
            a.shift()
        } else {
            res.push(b[0])
            b.shift()
        }
    }
    
    if(a.length){
        res = res.concat(a)
    } else {
        res = res.concat(b)
    }
    
    return res
}

// 功能测试
const arr = [4, 3, 6, 2, 5, 7, 9, 8, 1]
console.log(mergeSort(arr)) // [1, 2, 3, 4, 5, 6, 7, 8, 9]

原理

归并排序的核心思想是"分而治之"，主要包含两个步骤：

  1. 分：将数组不断二分，直到每个子数组只有一个元素（单个元素自然是有序的）
  2. 治：将有序的子数组两两合并，直到合并成一个完整的有序数组

主要就是分为两步

  • 分割：将待排序的线性表不断地切分成若干个子表，直到每个子表只包含一个元素，这时，可以认为只包含一个元素的子表是有序表。
  • 归并：将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表。

算法步骤

  1. 分解阶段：
    • 将数组从中间分成两个子数组
    • 递归地对每个子数组进行分解，直到每个子数组只有一个元素
  2. 合并阶段：
    • 将两个有序的子数组合并成一个有序数组
    • 比较两个子数组的元素，按顺序取出较小的元素放入结果数组
    • 如果其中一个子数组已经全部取出，则将另一个子数组的剩余元素直接复制到结果数组

时间复杂度分析

  • 最好时间复杂度：O(n log n)
  • 平均时间复杂度：O(n log n)
  • 最坏时间复杂度：O(n log n)
  • 空间复杂度：O(n) - 需要额外的空间来存储合并的数组

优缺点分析

优点

  1. 时间复杂度稳定：在各种情况下都是O(n log n)
  2. 稳定排序：相等元素的相对顺序保持不变
  3. 适合大规模数据：对于大数据集效率较高
  4. 可并行化：分解阶段可以并行处理

缺点

  1. 空间复杂度高：需要O(n)的额外空间
  2. 小规模数据性能不如插入排序：对于小数组，插入排序可能更高效
  3. 不是原地排序：需要额外的存储空间

JavaScript实现

基础实现

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>归并排序</title>
</head>

<body>
    <script>
    // 解法1 归并排序
    const merge=(left,right)=>{
        let result = [];
        let leftIndex = 0;
        let rightIndex = 0;
        while (leftIndex < left.length && rightIndex < right.length) {
            if(left[leftIndex]<right[rightIndex]){
                result.push(left[leftIndex])
                leftIndex++;
            }else{
                result.push(right[rightIndex])
                rightIndex++;
            }
        }
        return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
    };
    const  mergeSort=(arr)=> {
        // 数组长度小于等于1，则已经有序
        if(arr.length<=1){
            return arr;
        }
        // 分解阶段：将数组分成两半
        const middle=Math.floor(arr.length / 2);
        const left =arr.slice(0,middle);
        const right =arr.slice(middle);
        return merge(mergeSort(left),mergeSort(right))
    }

    // 示例使用
    const arr = [38, 27, 43, 3, 9, 82, 10];
    console.log("原始数组:", arr);
    console.log("排序后数组:", mergeSort(arr));
    </script>
</body>

</html>

优化1-对小数组使用插入排序

归并排序的方式比较适合于大数组，这种时候小数组我们可以额外使用插入排序进行优化

当数组长度小于某个阈值（如10-20）时，使用插入排序而不是继续递归归并排序
插入排序在小数组上表现通常比归并排序更好

设置阈值以后

// 2 优化-小数组使用插入排序
    const INSERTION_SORT_THRESHOLD = 10;
    const insertionSort = (arr) => {
        for (let i = 1; i < arr.length; i++) {
            let key = arr[i];
            let j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
        return arr;
    };
    const merge=(left,right)=>{
        let result = [];
        let leftIndex = 0;
        let rightIndex = 0;
        while (leftIndex < left.length && rightIndex < right.length) {
            if(left[leftIndex]<right[rightIndex]){
                result.push(left[leftIndex])
                leftIndex++;
            }else{
                result.push(right[rightIndex])
                rightIndex++;
            }
        }
        return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
    };
    const  mergeSort=(arr)=> {
        // 数组长度小于等于1，则已经有序
        if(arr.length<=INSERTION_SORT_THRESHOLD){
            return insertionSort([...arr]);
        }
        // 分解阶段：将数组分成两半
        const middle=Math.floor(arr.length / 2);
        const left =arr.slice(0,middle);
        const right =arr.slice(middle);
        return merge(mergeSort(left), mergeSort(right));
    }

优化合并过程

检查左右数组是否已经有序，避免不必要的比较

 // 3-优化合并过程
    // 检查左右数组是否已经有序，避免不必要的比较
    // 这里感觉其实就是各种排序之间的特性进行优化
    const INSERTION_SORT_THRESHOLD = 10;
    const insertionSort = (arr) => {
        for (let i = 1; i < arr.length; i++) {
            let key = arr[i];
            let j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
        return arr;
    };
    const merge=(left,right)=>{
        // 检查是否可以直接合并
        if (left[left.length - 1] <= right[0]) {
            return left.concat(right);
        }
        if (right[right.length - 1] <= left[0]) {
            return right.concat(left);
        }
        let result = [];
        let leftIndex = 0;
        let rightIndex = 0;
        while (leftIndex < left.length && rightIndex < right.length) {
            if(left[leftIndex]<right[rightIndex]){
                result.push(left[leftIndex])
                leftIndex++;
            }else{
                result.push(right[rightIndex])
                rightIndex++;
            }
        }
        return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
    };
    const  mergeSort=(arr)=> {
        // 数组长度小于等于1，则已经有序
        if(arr.length<=INSERTION_SORT_THRESHOLD){
            return insertionSort([...arr]);
        }
        // 分解阶段：将数组分成两半
        const middle=Math.floor(arr.length / 2);
        const left =arr.slice(0,middle);
        const right =arr.slice(middle);
        return merge(mergeSort(left), mergeSort(right));
    }

优化-预先分配结果数组空间

// 预先分配结果数组空间
    const INSERTION_SORT_THRESHOLD = 10;
    const insertionSort = (arr) => {
        for (let i = 1; i < arr.length; i++) {
            let key = arr[i];
            let j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
        return arr;
    };
    const merge=(left,right)=>{
        // 检查是否可以直接合并
        if (left[left.length - 1] <= right[0]) {
            return left.concat(right);
        }
        if (right[right.length - 1] <= left[0]) {
            return right.concat(left);
        }
         // 预先分配结果数组空间
        const result = new Array(left.length + right.length);
        let leftIndex = 0, rightIndex = 0, resultIndex = 0;

        while (leftIndex < left.length && rightIndex < right.length) {
            result[resultIndex++] = left[leftIndex] < right[rightIndex] 
            ? left[leftIndex++] 
            : right[rightIndex++];
        }
         // 处理剩余元素
        while (leftIndex < left.length) {
            result[resultIndex++] = left[leftIndex++];
        }
        while (rightIndex < right.length) {
            result[resultIndex++] = right[rightIndex++];
        }
        
        return result;
    };
    const  mergeSort=(arr)=> {
        // 数组长度小于等于1，则已经有序
        if(arr.length<=INSERTION_SORT_THRESHOLD){
            return insertionSort([...arr]);
        }
        // 分解阶段：将数组分成两半
        const middle=Math.floor(arr.length / 2);
        const left =arr.slice(0,middle);
        const right =arr.slice(middle);
        return merge(mergeSort(left), mergeSort(right));
    }

优化5-避免不必要的数组复制-使用索引而不是slice来减少内存分配

 const mergeSort = (arr, start = 0, end = arr.length) => {
        // 数组长度小于阈值，使用插入排序
        if (end - start <= INSERTION_SORT_THRESHOLD) {
            return insertionSort(arr.slice(start, end));
        }
        
        const middle = Math.floor((start + end) / 2);
        const left = mergeSort(arr, start, middle);
        const right = mergeSort(arr, middle, end);
        return merge(left, right);
    };

优化-使用迭代而非递归实现

const INSERTION_SORT_THRESHOLD = 10;
    const insertionSort = (arr) => {
        for (let i = 1; i < arr.length; i++) {
            let key = arr[i];
            let j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
        return arr;
    };
    const merge = (arr, temp, left, mid, right) => {
        // 检查是否已经有序
        if (arr[mid - 1] <= arr[mid]) {
            return;
        }
        
        // 合并两个有序区间
        let i = left, j = mid, k = left;
        while (i < mid && j < right) {
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        while (i < mid) {
            temp[k++] = arr[i++];
        }
        while (j < right) {
            temp[k++] = arr[j++];
        }
        
        // 将合并结果复制回原数组
        for (let idx = left; idx < right; idx++) {
            arr[idx] = temp[idx];
        }
    };
    const mergeSort = (arr) => {
        const n = arr.length;
        const temp = new Array(n);
        
        // 使用插入排序处理小数组
        for (let i = 0; i < n; i += INSERTION_SORT_THRESHOLD) {
            const end = Math.min(i + INSERTION_SORT_THRESHOLD, n);
            insertionSort(arr, i, end);
        }
        
        // 自底向上的归并排序
        for (let size = INSERTION_SORT_THRESHOLD; size < n; size *= 2) {
            for (let left = 0; left < n - size; left += 2 * size) {
                const mid = left + size;
                const right = Math.min(left + 2 * size, n);
                merge(arr, temp, left, mid, right);
            }
        }
        
        return arr;
    };

最终版本

const INSERTION_SORT_THRESHOLD = 10;

const insertionSort = (arr, start = 0, end = arr.length) => {
    for (let i = start + 1; i < end; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= start && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
};

const merge = (left, right) => {
    // 检查是否可以直接合并
    if (left[left.length - 1] <= right[0]) {
        return left.concat(right);
    }
    if (right[right.length - 1] <= left[0]) {
        return right.concat(left);
    }
    
    // 预先分配结果数组空间
    const result = new Array(left.length + right.length);
    let leftIndex = 0, rightIndex = 0, resultIndex = 0;
    
    while (leftIndex < left.length && rightIndex < right.length) {
        result[resultIndex++] = left[leftIndex] < right[rightIndex] 
            ? left[leftIndex++] 
            : right[rightIndex++];
    }
    
    // 处理剩余元素
    while (leftIndex < left.length) {
        result[resultIndex++] = left[leftIndex++];
    }
    while (rightIndex < right.length) {
        result[resultIndex++] = right[rightIndex++];
    }
    
    return result;
};

const mergeSort = (arr) => {
    // 数组长度小于阈值，使用插入排序
    if (arr.length <= INSERTION_SORT_THRESHOLD) {
        return insertionSort([...arr]);
    }
    
    // 分解阶段：将数组分成两半
    const middle = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, middle));
    const right = mergeSort(arr.slice(middle));
    return merge(left, right);
};
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
数据库 数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入