【金九银十】笔试通关 + 小学生都能学会的归并排序

归并排序（Merge Sort）是一种经典的排序算法，由约翰·冯·诺依曼（John von Neumann）在1945年首次提出。它基于“分治法”策略，通过将数据分成更小的部分，然后将这些部分分别排序，最后将已排序的部分合并成一个最终的排序结果。归并排序是一种稳定的排序算法，时间复杂度为 O(nlog⁡n)O(n log n)O(nlogn)，适用于大规模数据排序。

起源

归并排序的起源可以追溯到20世纪40年代。当时，计算机科学还处于萌芽阶段。约翰·冯·诺依曼是计算机科学的奠基人之一，他在1945年提出了归并排序。归并排序的提出是计算机科学历史上的一个重要里程碑，因为它提供了一种有效且易于实现的排序方法，并且其理论基础为后来的排序算法和分治策略奠定了基础。

算法原理

归并排序的主要步骤包括：

分解：将待排序的数组或列表分割成两个大致相等的部分。
解决：递归地对这两个部分进行归并排序，直到每个部分只包含一个元素（因为一个元素是自然有序的）。
合并：将两个已排序的部分合并成一个有序的部分。

详细解释

1. 分解

初始时，将整个数组分为两个子数组。这个分解过程递归进行，直到每个子数组的长度为1。
例如，对于数组 [38, 27, 43, 3, 9, 82, 10]，第一次分解会得到 [38, 27, 43] 和 [3, 9, 82, 10]。接着，将这两个子数组再次分解，直到每个子数组只有一个元素或为空。

2. 解决

一旦每个子数组都只包含一个元素，开始将这些子数组合并。每个子数组已经是有序的，因为只有一个元素。
通过递归地合并子数组，逐步构建更大的已排序部分。例如，将 [27] 和 [43] 合并成 [27, 43]。

3. 合并

合并操作涉及将两个已排序的子数组合并成一个有序的子数组。
比较两个子数组的第一个元素，将较小的元素添加到结果数组中。重复此过程，直到所有元素都被添加到结果数组中。
例如，合并 [27, 38, 43] 和 [3, 9, 10, 82] 会得到 [3, 9, 10, 27, 38, 43, 82]。

文字描述过程

初始阶段：假设我们有一个需要排序的数组。首先将数组分成两个部分，左半部分和右半部分。
递归排序：对每一部分进行归并排序。分解的过程一直进行，直到每个部分都包含一个元素或为空，这些部分自然有序。
合并阶段：从最小的部分开始，逐步合并相邻的已排序部分。比较两个部分的元素，将较小的元素添加到新数组中，直到所有元素都被合并成一个有序的数组。
完成：最终，整个数组会被合并成一个完全排序的数组，完成排序过程。

动态实现

下面是使用 JavaScript 和 HTML 实现归并排序的动态演示：

HTML 代码

代码语言：html复制

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>归并排序演示</title>
    <style>
        body {
            font-family: Arial, sans-serif;
            text-align: center;
            background-color: #282c34;
            color: #61dafb;
        }
        h1 {
            margin-top: 20px;
            margin-bottom: 20px;
        }
        #container {
            display: flex;
            justify-content: center;
            align-items: flex-end;
            height: 400px;
            margin: 0 auto;
            border: 2px solid #61dafb;
            background-color: #1e2024;
            overflow: hidden;
        }
        .bar {
            display: inline-block;
            width: 30px;
            margin: 2px;
            background-color: #61dafb;
            color: white;
            text-align: center;
            transition: height 0.5s ease, background-color 0.5s ease;
            position: relative;
            overflow: hidden;
        }
        .bar-label {
            position: absolute;
            bottom: 0;
            width: 100%;
            background: rgba(0, 0, 0, 0.7);
            color: white;
            font-size: 12px;
            line-height: 30px;
        }
        button {
            background-color: #61dafb;
            border: none;
            padding: 10px 20px;
            margin-top: 20px;
            color: #282c34;
            font-size: 16px;
            cursor: pointer;
            transition: background-color 0.3s ease;
        }
        button:hover {
            background-color: #4fa3b5;
        }
    </style>
</head>
<body>
    <h1>归并排序演示</h1>
    <div id="container"></div>
    <button onclick="startSort()">开始排序</button>
    <script src="/js/merge-sort.js"></script>
</body>
</html>

JavaScript 代码

代码语言：javascript复制

// 归并排序主函数
function mergeSort(arr) {
    if (arr.length <= 1) return 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);
}

// 合并两个排序好的数组
function merge(left, right) {
    const 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));
}

// 初始化数据并渲染
function initializeData() {
    const array = [38, 27, 43, 3, 9, 82, 10];
    renderArray(array);
}

// 渲染数组
function renderArray(arr, highlight = []) {
    const container = document.getElementById('container');
    container.innerHTML = '';
    arr.forEach((value, index) => {
        const bar = document.createElement('div');
        bar.className = 'bar';
        bar.style.height = `${value * 3}px`;
        if (highlight.includes(index)) {
            bar.style.backgroundColor = '#ff6347'; // 高亮颜色
        }
        bar.innerHTML = `<div class="bar-label">${value}</div>`;
        container.appendChild(bar);
    });
}

// 动态展示排序过程
async function animateSort(arr) {
    if (arr.length <= 1) return arr;

    const middle = Math.floor(arr.length / 2);
    const left = arr.slice(0, middle);
    const right = arr.slice(middle);

    renderArray(arr, [0, arr.length - 1]); // 高亮显示边界

    await new Promise(resolve => setTimeout(resolve, 500)); // 延时展示

    const leftSorted = await animateSort(left);
    const rightSorted = await animateSort(right);

    const merged = merge(leftSorted, rightSorted);
    renderArray(merged);

    await new Promise(resolve => setTimeout(resolve, 500)); // 延时展示

    return merged;
}

// 开始排序
function startSort() {
    const array = [38, 27, 43, 3, 9, 82, 10];
    animateSort(array);
}

// 页面加载时初始化数据
window.onload = initializeData;

这个代码示例展示了如何用 HTML 和 JavaScript 实现归并排序的动态演示。在这个演示中，按下“开始排序”按钮会触发归并排序，并通过动态更新页面上的条形图来可视化排序过程。