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

2024-09-09 08:38:39 浏览数 (1)

算法原理

冒泡排序（Bubble Sort）是一种简单的排序算法，它通过重复遍历待排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来，直到整个数列有序。冒泡排序的名字来源于排序过程中较小的元素会像气泡一样逐渐“浮”到数列的顶端，而较大的元素则“沉”到底部

其原理是通过多次比较和交换相邻元素，将较大的元素逐步“冒泡”到数组的末尾。具体步骤如下：

  1. 比较相邻元素：从数组的第一个元素开始，比较每一对相邻的元素，如果前一个元素比后一个大，则交换它们的位置。
  2. 重复操作：对每一对相邻元素都进行上述比较和交换操作，这样一趟下来，最大或最小的元素就会移动到数组末尾。
  3. 缩小范围：每一趟结束后，将末尾已经排好序的元素排除出下一趟比较。
  4. 重复步骤1和2：不断重复上述过程，直到没有任何元素需要交换，排序完成。

实例分析

成绩排序：在学校的期末考试中，老师会根据学生的成绩进行排名。这个过程也可以看作是冒泡排序的应用，成绩较低的学生会逐渐“冒泡”到排名的后面。

假设我们有一个成绩 [5, 3, 8, 4, 2]，我们用冒泡排序对它进行升序排列：

  • 第一趟：
    • 比较 5 和 3，5 > 3，交换，数组变为 [3, 5, 8, 4, 2]
    • 比较 5 和 8，5 < 8，不交换，数组不变 [3, 5, 8, 4, 2]
    • 比较 8 和 4，8 > 4，交换，数组变为 [3, 5, 4, 8, 2]
    • 比较 8 和 2，8 > 2，交换，数组变为 [3, 5, 4, 2, 8]
  • 第二趟：
    • 比较 3 和 5，3 < 5，不交换，数组不变 [3, 5, 4, 2, 8]
    • 比较 5 和 4，5 > 4，交换，数组变为 [3, 4, 5, 2, 8]
    • 比较 5 和 2，5 > 2，交换，数组变为 [3, 4, 2, 5, 8]
  • 第三趟：
    • 比较 3 和 4，3 < 4，不交换，数组不变 [3, 4, 2, 5, 8]
    • 比较 4 和 2，4 > 2，交换，数组变为 [3, 2, 4, 5, 8]
  • 第四趟：
    • 比较 3 和 2，3 > 2，交换，数组变为 [2, 3, 4, 5, 8]

最终数组排序完成，变为 [2, 3, 4, 5, 8]。

动态实现

代码语言：javascript复制
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Bubble Sort Visualization</title>
    <style>
        body {
            font-family: 'Arial', sans-serif;
            background-color: #f0f2f5;
            display: flex;
            justify-content: center;
            align-items: center;
            height: 100vh;
            margin: 0;
            flex-direction: column;
        }

        h1 {
            color: #333;
            margin-bottom: 20px;
            font-size: 24px;
            letter-spacing: 1px;
        }

        #array-container {
            display: flex;
            justify-content: center;
            align-items: flex-end;
            height: 300px;
            width: 80%;
            background-color: #ffffff;
            border-radius: 10px;
            box-shadow: 0 4px 8px rgba(0, 0, 0, 0.1);
            padding: 20px;
            margin-bottom: 20px;
        }

        .array-bar {
            display: inline-block;
            width: 40px;
            margin: 0 5px;
            background-color: #3498db;
            text-align: center;
            color: white;
            font-weight: bold;
            border-radius: 5px;
            transition: background-color 0.3s ease;
        }

        .array-bar:hover {
            background-color: #2980b9;
        }

        button {
            padding: 10px 20px;
            font-size: 16px;
            font-weight: bold;
            color: white;
            background-color: #e74c3c;
            border: none;
            border-radius: 5px;
            cursor: pointer;
            transition: background-color 0.3s ease;
        }

        button:hover {
            background-color: #c0392b;
        }

        button:active {
            transform: scale(0.98);
        }
    </style>
</head>
<body>
    <h1>Bubble Sort Visualization</h1>
    <div id="array-container"></div>
    <button onclick="bubbleSort()">Sort</button>

    <script>
        const array = [5, 3, 8, 4, 2];
        const container = document.getElementById('array-container');

        function displayArray(arr) {
            container.innerHTML = '';
            arr.forEach(value => {
                const bar = document.createElement('div');
                bar.className = 'array-bar';
                bar.style.height = `${value * 20}px`;
                bar.innerText = value;
                container.appendChild(bar);
            });
        }

        function sleep(ms) {
            return new Promise(resolve => setTimeout(resolve, ms));
        }

        async function bubbleSort() {
            let len = array.length;
            for (let i = 0; i < len - 1; i  ) {
                for (let j = 0; j < len - i - 1; j  ) {
                    if (array[j] > array[j   1]) {
                        // Swap elements
                        let temp = array[j];
                        array[j] = array[j   1];
                        array[j   1] = temp;
                        displayArray(array);
                        await sleep(500); // Pause for visualization
                    }
                }
            }
        }

        // Initial display
        displayArray(array);
    </script>
</body>
</html>

展示效果

算法部分代码

代码中与冒泡排序算法相关的部分：

代码语言：javascript复制
async function bubbleSort() {
    let len = array.length;
    for (let i = 0; i < len - 1; i  ) {
        for (let j = 0; j < len - i - 1; j  ) {
            if (array[j] > array[j   1]) {
                // Swap elements
                let temp = array[j];
                array[j] = array[j   1];
                array[j   1] = temp;
                displayArray(array);
                await sleep(500); 
            }
        }
    }
}

let len = array.length;

  • 这行代码获取数组的长度，并将其存储在变量 len 中。在后续的排序操作中，这个长度用于控制循环的次数。

外层 for 循环：for (let i = 0; i < len - 1; i )

  • 这个循环控制一共需要多少趟排序。每一趟排序后，最大（或最小）的元素会被移到数组的末尾，因而下一趟排序时不需要再考虑最后的那个元素。因此，循环的次数是 len - 1。

内层 for 循环：for (let j = 0; j < len - i - 1; j )

  • 这个循环遍历数组的每一对相邻元素，进行比较和交换操作。因为每次外层循环结束后，数组末尾的元素已经是有序的，所以内层循环的范围逐渐缩小，每次减少一位（即 len - i - 1）。

比较和交换：if (array[j] > array[j 1])

  • 这行代码比较当前元素 array[j] 和下一个元素 array[j 1] 的大小。
  • 如果当前元素大于下一个元素，说明这两个元素顺序不对，需要交换它们的位置。

交换元素：let temp = array[j]; array[j] = array[j 1]; array[j 1] = temp;

  • 交换两个元素的位置。通过一个临时变量 temp 来保存 array[j] 的值，然后将 array[j 1] 的值赋给 array[j]，最后将 temp（即原来的 array[j] 的值）赋给 array[j 1]。这样就实现了两个相邻元素的交换。

更新显示：displayArray(array);

  • 这行代码在每次元素交换后调用 displayArray 函数，将当前数组状态渲染到页面上。这样可以动态展示排序过程。

延时：await sleep(500);

  • 这行代码通过 sleep 函数实现每次交换后的延时，使得排序过程可视化时更加清晰，观众可以看到一步步的排序操作。
  • sleep(500) 表示等待 500 毫秒，await 关键字保证 JavaScript 在继续执行循环前会等待这段时间。

算法运行过程

每趟外层循环中，内层循环会依次比较和交换相邻的元素，把当前未排序部分的最大值“冒泡”到数组的末尾。内层循环结束后，最大的元素已经移动到正确的位置。外层循环的次数决定了整体排序的完成。

例如：

  • 第一趟比较和交换完成后，最大的元素位于数组末尾。
  • 第二趟再次通过比较和交换，把次大的元素移到倒数第二的位置，依此类推。

最终，当外层循环结束后，数组就完全有序了。

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

0 人点赞