【金九银十】笔试通关 + 小学生都能学会的冒泡排序
【摘要】 冒泡排序（Bubble Sort）是一种简单的排序算法，它通过重复遍历待排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来，直到整个数列有序。冒泡排序的名字来源于排序过程中较小的元素会像气泡一样逐渐“浮”到数列的顶端，而较大的元素则“沉”到底部
算法原理
冒泡排序（Bubble Sort）是一种简单的排序算法，它通过重复遍历待排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来，直到整个数列有序。冒泡排序的名字来源于排序过程中较小的元素会像气泡一样逐渐“浮”到数列的顶端，而较大的元素则“沉”到底部
其原理是通过多次比较和交换相邻元素，将较大的元素逐步“冒泡”到数组的末尾。具体步骤如下：
- 比较相邻元素：从数组的第一个元素开始，比较每一对相邻的元素，如果前一个元素比后一个大，则交换它们的位置。
- 重复操作：对每一对相邻元素都进行上述比较和交换操作，这样一趟下来，最大或最小的元素就会移动到数组末尾。
- 缩小范围：每一趟结束后，将末尾已经排好序的元素排除出下一趟比较。
- 重复步骤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]
- 比较 5 和 3，5 > 3，交换，数组变为
- 第二趟：
- 比较 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 和 5，3 < 5，不交换，数组不变
- 第三趟：
- 比较 3 和 4，3 < 4，不交换，数组不变
[3, 4, 2, 5, 8] - 比较 4 和 2，4 > 2，交换，数组变为
[3, 2, 4, 5, 8]
- 比较 3 和 4，3 < 4，不交换，数组不变
- 第四趟：
- 比较 3 和 2，3 > 2，交换，数组变为
[2, 3, 4, 5, 8]
- 比较 3 和 2，3 > 2，交换，数组变为
最终数组排序完成，变为 [2, 3, 4, 5, 8]。
动态实现
<!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>
展示效果
算法部分代码
代码中与冒泡排序算法相关的部分：
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 在继续执行循环前会等待这段时间。
算法运行过程
每趟外层循环中，内层循环会依次比较和交换相邻的元素，把当前未排序部分的最大值“冒泡”到数组的末尾。内层循环结束后，最大的元素已经移动到正确的位置。外层循环的次数决定了整体排序的完成。
例如：
- 第一趟比较和交换完成后，最大的元素位于数组末尾。
- 第二趟再次通过比较和交换，把次大的元素移到倒数第二的位置，依此类推。
最终，当外层循环结束后，数组就完全有序了。
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）