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

2024-09-13 09:26:13 浏览数 (1)

起源

插入排序的起源可以追溯到早期计算机科学的发展。它是一种古老且基本的排序算法，其基本思想可以追溯到手工排序的方法。最早的文献中并没有详细说明插入排序的发明者，但它在各种早期的计算机排序算法中被广泛使用。

  • 历史背景：插入排序的算法思想类似于在手工排序扑克牌的过程。在扑克牌游戏中，玩家会将一张新牌插入到已排序的牌堆中，保持牌堆的有序性。
  • 发展历程：插入排序作为一种简单的排序方法，适用于小规模的数据集或部分已排序的数据。随着计算机科学的进步，插入排序逐渐被更高效的排序算法（如快速排序、归并排序等）所取代，但它在实际应用中仍然有其独特的优势，如在小数据集或部分已排序的数组中表现良好。

扑克牌的排序

想象你正在与朋友玩扑克牌。每当你拿到一张新牌时，你需要将它插入到已经排序好的手牌中。你会从最左边开始，将新牌与当前手牌中的牌进行比较，将比新牌大的牌移动到右边，直到找到一个合适的位置插入新牌。这个过程就是插入排序的核心思想。

假设你的手中有五张扑克牌，已经按升序排好。你现在得到了一张新牌，你会把它拿到手中，按照大小顺序逐一将它插入到已经排序好的手牌中，直到手中的所有牌都保持有序状态。这种操作在计算机中被称为插入排序，其中每一次插入操作都确保了已排序部分的有序性。

通过这样的比喻，我们可以更容易理解插入排序的原理和过程，感受到其在实际应用中的直观性和易用性。

算法原理

插入排序是一种简单的排序算法，基本思想是将数组分为已排序和未排序两部分。初始时，已排序部分只有一个元素，未排序部分包含其余元素。算法从未排序部分取出元素，将其插入到已排序部分的合适位置，重复这一过程直到所有元素都被插入到已排序部分中。

具体步骤

  1. 从数组的第二个元素开始（第一个元素默认是已排序部分的一部分），将当前元素（key）与已排序部分的元素进行比较。
  2. 找到已排序部分中比当前元素大的位置，将这些元素向右移动一个位置。
  3. 将当前元素插入到找到的位置。
  4. 继续对下一个元素重复以上步骤，直到整个数组都被排序。

时间复杂度

  • 最坏情况：(O(n^2))（当输入数组是反向排序时）
  • 最好情况：(O(n))（当输入数组已经是排序好的）
  • 平均情况：(O(n^2))

空间复杂度

  • (O(1))（插入排序是原地排序算法）

实例分析

以数组 [5, 2, 9, 1, 5, 6] 为例进行插入排序：

开始排序：

  • 假设第一个元素 5 已经在排序部分中（已排序部分为 [5]）。

处理第二个元素 2：

  • 比较 2 和 5，由于 2 小于 5，将 5 向后移动，并将 2 插入到最前面。
  • 数组变为 [2, 5, 9, 1, 5, 6]。

处理第三个元素 9：

  • 比较 9 和 5，由于 9 大于 5，9 保持在当前位置。
  • 数组仍为 [2, 5, 9, 1, 5, 6]。

处理第四个元素 1：

  • 比较 1 与已排序部分 [2, 5, 9]，将 2、5 和 9 向后移动，将 1 插入到最前面。
  • 数组变为 [1, 2, 5, 9, 5, 6]。

处理第五个元素 5：

  • 比较 5 与 9，将 9 向后移动。5 保持在当前位置（5 和 5 互相比较）。
  • 数组变为 [1, 2, 5, 5, 9, 6]。

处理第六个元素 6：

  • 比较 6 与 9，将 9 向后移动，将 6 插入到正确位置。
  • 数组变为 [1, 2, 5, 5, 6, 9]。

最终得到排序后的数组 [1, 2, 5, 5, 6, 9]。

动态实现

代码语言：javascript复制
<!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;
            display: flex;
            flex-direction: column;
            align-items: center;
            justify-content: center;
            height: 100vh;
            margin: 0;
            background-color: #f4f4f4;
        }
        h1 {
            margin-bottom: 20px;
        }
        #array-container {
            display: flex;
            align-items: flex-end;
            justify-content: center;
            width: 80%;
            max-width: 600px;
            height: 300px;
            margin-bottom: 20px;
            position: relative;
        }
        .array-bar {
            width: 40px;
            background-color: #4caf50;
            color: white;
            text-align: center;
            line-height: 30px;
            border-radius: 5px;
            transition: all 0.5s ease;
            position: relative;
            margin: 2px;
        }
        .array-bar::after {
            content: '';
            display: block;
            width: 100%;
            height: 100%;
            background: rgba(255, 255, 255, 0.3);
            border-radius: 5px;
            position: absolute;
            top: 0;
            left: 0;
            pointer-events: none;
        }
        button {
            padding: 10px 20px;
            font-size: 16px;
            color: white;
            background-color: #2196f3;
            border: none;
            border-radius: 5px;
            cursor: pointer;
            transition: background-color 0.3s ease;
        }
        button:hover {
            background-color: #1976d2;
        }
    </style>
</head>
<body>
    <h1>插入排序动态展示</h1>
    <div id="array-container"></div>
    <button onclick="sortArray()">开始排序</button>

    <script>
        let array = [5, 2, 9, 1, 5, 6];
        const container = document.getElementById('array-container');

        function renderArray(arr) {
            container.innerHTML = '';
            arr.forEach(value => {
                const bar = document.createElement('div');
                bar.className = 'array-bar';
                bar.style.height = `${value * 30}px`;
                bar.style.backgroundColor = '#4caf50'; // Default color
                bar.textContent = value;
                container.appendChild(bar);
            });
        }

        async function sortArray() {
            for (let i = 1; i < array.length; i  ) {
                let key = array[i];
                let j = i - 1;
                
                while (j >= 0 && array[j] > key) {
                    array[j   1] = array[j];
                    renderArray(array);
                    await new Promise(resolve => setTimeout(resolve, 500));

                    // Highlight the current bar being moved
                    const bars = container.getElementsByClassName('array-bar');
                    bars[j   1].style.backgroundColor = '#f44336'; // Color change
                    if (j >= 0) {
                        bars[j].style.backgroundColor = '#ffeb3b'; // Color change
                    }
                    await new Promise(resolve => setTimeout(resolve, 500));
                    bars[j   1].style.backgroundColor = '#4caf50'; // Reset color
                    if (j >= 0) {
                        bars[j].style.backgroundColor = '#4caf50'; // Reset color
                    }
                    j--;
                }
                array[j   1] = key;
                renderArray(array);
                await new Promise(resolve => setTimeout(resolve, 500));
            }
        }

        renderArray(array);
    </script>
</body>
</html>

解释部分的代码

下面是 sortArray 函数的详细解释，这部分代码负责执行插入排序算法并在页面上动态展示排序过程。

代码语言：javascript复制
async function sortArray() {
    // 外层循环：从第二个元素开始，逐个处理未排序的元素
    for (let i = 1; i < array.length; i  ) {
        let key = array[i]; // 当前元素
        let j = i - 1; // 已排序部分的最后一个元素索引
        
        // 内层循环：将当前元素插入到已排序部分的合适位置
        while (j >= 0 && array[j] > key) {
            array[j   1] = array[j]; // 将大于当前元素的元素向后移动
            renderArray(array); // 更新页面显示
            await new Promise(resolve => setTimeout(resolve, 500)); // 等待 500 毫秒
            
            // 高亮显示当前正在移动的方块
            const bars = container.getElementsByClassName('array-bar');
            bars[j   1].style.backgroundColor = '#f44336'; // 当前方块变红
            if (j >= 0) {
                bars[j].style.backgroundColor = '#ffeb3b'; // 前一个方块变黄
            }
            await new Promise(resolve => setTimeout(resolve, 500)); // 等待 500 毫秒
            bars[j   1].style.backgroundColor = '#4caf50'; // 当前方块恢复原色
            if (j >= 0) {
                bars[j].style.backgroundColor = '#4caf50'; // 前一个方块恢复原色
            }
            j--; // 继续检查前面的元素
        }
        array[j   1] = key; // 插入当前元素到正确位置
        renderArray(array); // 更新页面显示
        await new Promise(resolve => setTimeout(resolve, 500)); // 等待 500 毫秒
    }
}

详细说明

外层循环：for (let i = 1; i < array.length; i )：从第二个元素（索引 1）开始，逐步处理数组中的每个元素。第一个元素默认已经是排序好的。

初始化 key 和 j：

  • let key = array[i];：当前处理的元素，即待插入到已排序部分中的元素。
  • let j = i - 1;：已排序部分的最后一个元素的索引。

内层循环：

  • while (j >= 0 && array[j] > key)：检查已排序部分中的元素是否大于 key。如果是，则将这些元素向后移动，为 key 找到插入位置。
  • array[j 1] = array[j];：将大于 key 的元素向后移动一个位置。
  • renderArray(array);：调用 renderArray 函数更新页面显示，确保排序过程可视化。
  • await new Promise(resolve => setTimeout(resolve, 500));：暂停 500 毫秒，以便用户可以看到排序过程的每一步。

高亮显示：

  • 在每次元素移动时，通过改变方块的颜色来高亮显示当前操作的方块。这样可以更直观地展示排序过程。
  • bars[j 1].style.backgroundColor = '#f44336';：将当前方块的颜色设置为红色，突出显示正在移动的方块。
  • if (j >= 0) { bars[j].style.backgroundColor = '#ffeb3b'; }：将前一个方块的颜色设置为黄色，强调比较操作。
  • 颜色恢复操作：bars[j 1].style.backgroundColor = '#4caf50'; 和 bars[j].style.backgroundColor = '#4caf50'; 将方块颜色恢复为原始颜色。

插入元素：

  • array[j 1] = key;：将 key 插入到已排序部分的正确位置。
  • 再次调用 renderArray(array) 更新页面显示，反映当前的排序状态。

继续处理下一个元素：

  • 外层循环继续处理下一个元素，直到整个数组排序完成。

这段代码实现了插入排序的基本算法，并通过动态效果展示了排序的过程，使其更加直观和易于理解。

腾讯技术创作特训营S9金九银十 插入排序

0 人点赞