当前位置：首页 > ds >正文

LeetCode-多语言实现冒泡排序以及算法优化改进

ds 2025/7/15 20:57:14

一、冒泡排序算法

二、应用场景/前提条件

🌈 优点

📢 缺点

三、经典算法实现并优化改进

方法一：记录最后一次交换位置，下一轮只遍历到该位置

方法二：添加标志位跟踪是否发生交换，无交换则提前终止（针对大部分有序的数组）

方法三：鸡尾酒排序（双向冒泡排序）

四、习题演练

测验

一、冒泡排序算法

冒泡排序（Bubble Sort）是一种简单直观的排序算法，其基本思想是：在待排序的一组数中，将相邻的两个数进行比较，若前面的数比后面的数大就交换两数，否则不交换；如此重复遍历下去，直到没有再需要交换的元素，最终完成排序。由此可得，在排序过程中，大的数据往下沉，小的数据往上浮，就像水中气泡上升一样，于是将这种排序算法形象地称为冒泡排序。

时间复杂度: 最佳 O(n) | 平均 O(n²) | 最差 O(n²)

空间复杂度: O(1)

稳定性:稳定（相等元素不交换）

二、应用场景/前提条件

适用于小规模数据
对几乎已排序的数据效率较高

🌈 优点

代码简单，容易实现
适合小规模数据排序
对于几乎已经排好序的数据，效率较高
稳定的排序算法

📢 缺点

时间复杂度高，为O(n²)
随着元素数量增加，效率急剧下降
每次只能将一个元素移动到其最终位置，效率不高

三、经典算法实现并优化改进

相较于传统的实现方法来说，有几个可以优化的点，以下使用JS实现演示：

方法一：记录最后一次交换位置，下一轮只遍历到该位置

<!DOCTYPE html>
<html lang="en">
<head><meta charset="UTF-8"><title>JavaScript 冒泡排序</title>
</head>
<script>function bubbleSort(arr) {let i = arr.length - 1;//设置初始比较范围到数组末尾while(i > 0){ // 外层循环控制排序轮数,当i = 0时，表示没有发生交换，排序完成let position = 0;for (let j = 0; j < i; j++) { // 遍历未排序部分if(arr[j] > arr[ j+ 1]){ // 比较相邻元素position = j; //记录最后一次交换的位置let temp = arr[j + 1];arr[j + 1] = arr[j];arr[j] = temp; // 使用临时变量temp交换两个元素的位置}}i = position; // 下一轮只需比较到上次最后交换的位置,后续每轮都会将当前未排序部分的最大值"冒泡"到正确位置，比较范围逐渐缩小（由i = position控制）console.log(arr.toString());}return arr;}let array = [59 , 34 , 25 , 67 ,15 ,87 ,10 ,99 ,3 ,45]let res_arr = bubbleSort(array)console.log("使用冒泡排序算法的最终排序结果是："+ res_arr)
</script>
</html>

初始数组：[59, 34, 25, 67, 15, 87, 10, 99, 3, 45]

第1轮遍历（i=9）：

比较59和34 → 交换 → [34,59,25,67,15,87,10,99,3,45]
比较59和25 → 交换 → [34,25,59,67,15,87,10,99,3,45]
比较59和67 → 不交换
比较67和15 → 交换 → [34,25,59,15,67,87,10,99,3,45]
比较67和87 → 不交换
比较87和10 → 交换 → [34,25,59,15,67,10,87,99,3,45]
比较87和99 → 不交换
比较99和3 → 交换 → [34,25,59,15,67,10,87,3,99,45]
比较99和45 → 交换 → [34,25,59,15,67,10,87,3,45,99]
最后一次交换位置：8（99和45交换的位置）

第2轮遍历（i=8）：

比较34和25 → 交换 → [25,34,59,15,67,10,87,3,45,99]
比较34和59 → 不交换
比较59和15 → 交换 → [25,34,15,59,67,10,87,3,45,99]
比较59和67 → 不交换
比较67和10 → 交换 → [25,34,15,59,10,67,87,3,45,99]
比较67和87 → 不交换
比较87和3 → 交换 → [25,34,15,59,10,67,3,87,45,99]
比较87和45 → 交换 → [25,34,15,59,10,67,3,45,87,99]
最后一次交换位置：7（87和45交换的位置）

依次类推.......

第7轮遍历（i=2）：

比较10和15 → 不交换
比较15和3 → 交换 → [10,3,15,25,34,45,59,67,87,99]
最后一次交换位置：1（15和3交换的位置）

第8轮遍历（i=1）：

比较10和3 → 交换 → [3,10,15,25,34,45,59,67,87,99]
最后一次交换位置：0（10和3交换的位置）

最终排序结果：[3,10,15,25,34,45,59,67,87,99]

整个过程共进行了8轮遍历，每次遍历都会将当前未排序部分的最大值"冒泡"到正确位置。随着排序的进行，需要比较的元素越来越少，效率逐渐提高。（这段代码的优化在于记录了最后一次交换的位置，避免了不必要的比较，提高了效率。每次循环后都会打印当前数组状态，方便观察排序过程。）

方法二：添加标志位跟踪是否发生交换，无交换则提前终止（针对大部分有序的数组）

function optimizedBubbleSort(arr) {const n = arr.length;for (let i = 0; i < n - 1; i++) {let swapped = false;for (let j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];swapped = true;}}// 如果没有交换操作，数组已排序完成if (!swapped) break;}return arr;
}

方法三：鸡尾酒排序（双向冒泡排序）

鸡尾酒排序是冒泡排序的一种变体，它从低到高然后从高到低来回排序，比冒泡排序的效率稍微高一点，在每次排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值（最大值和最小值），从而使排序次数几乎减少了一半。


<!DOCTYPE html>
<html lang="en">
<head><meta charset="UTF-8"><title>JavaScript 双向冒泡排序</title>
</head>
<script>function bubbleSort(arr) {let low = 0;let high = arr.length - 1;let temp;while (low < high) {// 正向遍历：找最大值for (let j = low; j < high; j++) {if (arr[j] > arr[j + 1]) {temp = arr[j + 1];arr[j + 1] = arr[j];arr[j] = temp;}}--high;console.log("正向结果：" + arr.toString());// 反向遍历：找最小值for (let j = high; j > low; j--) {if (arr[j] < arr[j - 1]) {temp = arr[j - 1];arr[j - 1] = arr[j];arr[j] = temp;}}++low;console.log("反向结果：" + arr.toString());}return arr;}let array = [59, 34, 25, 67, 15, 87, 10, 99, 3, 45];let res_arr = bubbleSort(array);console.log("最终排序结果：" + res_arr);
</script>
</html>

以下是数组 [59, 34, 25, 67, 15, 87, 10, 99, 3, 45] 的完整鸡尾酒手动排序过程：

‌排序过程‌

‌初始数组‌
[59, 34, 25, 67, 15, 87, 10, 99, 3, 45]
‌第1轮正向遍历‌（从左到右找最大值）
- 比较并交换：59↔34, 59↔25, 59↔67（不交换）, 67↔15, 67↔87（不交换）, 87↔10, 87↔99（不交换）, 99↔3, 99↔45
- ‌结果‌：[34, 25, 59, 15, 67, 10, 87, 3, 45, 99]（最大值99到末尾）
‌第1轮反向遍历‌（从右到左找最小值）
- 比较并交换：45↔3, 45↔87（不交换）, 87↔10, 87↔67（不交换）, 67↔15, 67↔59（不交换）, 59↔25, 59↔34（不交换）
- ‌结果‌：[3, 34, 25, 59, 15, 67, 10, 87, 45, 99]（最小值3到开头）
‌第2轮正向遍历‌
- 比较并交换：34↔25, 34↔59（不交换）, 59↔15, 59↔67（不交换）, 67↔10, 67↔87（不交换）, 87↔45
- ‌结果‌：[3, 25, 34, 15, 59, 10, 67, 45, 87, 99]
‌第2轮反向遍历‌
- 比较并交换：45↔67（不交换）, 67↔10, 67↔59（不交换）, 59↔15, 59↔34（不交换）, 34↔25
- ‌结果‌：[3, 10, 25, 15, 34, 59, 45, 67, 87, 99]
‌第3轮正向遍历‌
- 比较并交换：10↔25（不交换）, 25↔15, 25↔34（不交换）, 34↔59（不交换）, 59↔45, 59↔67（不交换）
- ‌结果‌：[3, 10, 15, 25, 34, 45, 59, 67, 87, 99]
‌第3轮反向遍历‌
- 比较并交换：59↔45（不交换）, 45↔34（不交换）, 34↔25（不交换）, 25↔15（不交换）
- ‌无交换发生，排序完成‌。

‌最终结果‌

[3, 10, 15, 25, 34, 45, 59, 67, 87, 99]‌

‌交替优化‌：每轮正向遍历将最大值推向右端，反向遍历将最小值推向左端。
‌提前终止‌：若某轮遍历无交换，说明数组已有序（如第3轮反向遍历后终止）。
‌效率对比‌：比传统冒泡排序减少约50%的轮次（本例仅需3轮双向遍历）。

优化思路：‌

‌双向遍历‌：传统冒泡排序只单向比较（从左到右），而这里同时从左到右和从右到左遍历，可以更快地将最大值和最小值"冒泡"到正确位置。
‌缩小范围‌：每次遍历后，未排序部分的边界（low和high）会动态调整，减少不必要的比较次数。

对于双向冒泡排序（鸡尾酒排序）的时间复杂度和空间复杂度分析如下：

⏳ 时间复杂度

💾 空间复杂度

‌原地排序‌：仅使用常数级临时变量（如 temp、low、high）
额外空间与输入规模无关 → ‌O(1)‌

🧠 核心结论

指标	双向冒泡排序
‌最坏时间复杂度‌	O(n²)
‌最好时间复杂度‌	O(n)
‌平均时间复杂度‌	O(n²)
‌空间复杂度‌	O(1)（原地排序）

⚠️ ‌说明‌：尽管双向遍历优化了部分场景（如两端元素有序时效率更高），但时间复杂度量级与传统冒泡排序一致。

四、习题演练

2023下半年软件设计师上午题——冒泡排序_冒泡排序选择题

下面推荐一些可以用来练手的 LeetCode 题目：

75. 颜色分类 - 可使用冒泡排序解决，但有更优的解法
283. 移动零 - 可用冒泡排序的思想将零元素"冒泡"到数组末尾
912. 排序数组 - 可使用冒泡排序，但因为数据规模较大，可能会超时

需要注意的是，使用冒泡排序不一定是最优解，仅使用冒泡排序也可能无法解决问题，不过这些题目都能够直接或间接体现冒泡排序核心思想，可以熟悉这个算法。

测验

冒泡排序是稳定的排序算法吗，为什么？
对于已经排好序的数组，优化版冒泡排序的时间复杂度是多少？
冒泡排序每一轮遍历后，数组尾部会有什么特点？
如何优化冒泡排序以提高效率？

测验答案

是的，冒泡排序是稳定的排序算法。因为只有当前一个元素大于后一个元素时才交换，相等元素不会改变相对位置。
对于已经排好序的数组，优化版冒泡排序的时间复杂度是O(n)。因为第一轮遍历不会发生交换，优化版会检测到这点并提前终止。
冒泡排序每一轮遍历后，数组尾部会有一个元素到达其最终位置，且是当前未排序部分中的最大元素。第i轮结束后，末尾i个元素已排好序。
优化冒泡排序的方法:
添加标志位跟踪是否发生交换，无交换则提前终止
记录最后一次交换位置，下一轮只遍历到该位置
使用双向冒泡(鸡尾酒排序)，同时将最大值上浮和最小值下沉

查看全文

http://www.xdnf.cn/news/13577.html