LeetCode-多語言實現冒泡排序以及算法優化改進

一、冒泡排序算法

二、應用場景/前提條件

🌈 優點

📢 缺點

三、經典算法實現并優化改進

方法一：記錄最后一次交換位置，下一輪只遍歷到該位置

方法二：添加標志位跟蹤是否發生交換，無交換則提前終止（針對大部分有序的數組）

方法三：雞尾酒排序（雙向冒泡排序）

四、習題演練

測驗

一、冒泡排序算法

????????冒泡排序（Bubble Sort）是一種簡單直觀的排序算法，其基本思想是：在待排序的一組數中，將相鄰的兩個數進行比較，若前面的數比后面的數大就交換兩數，否則不交換；如此重復遍歷下去，直到沒有再需要交換的元素，最終完成排序。由此可得，在排序過程中，大的數據往下沉，小的數據往上浮，就像水中氣泡上升一樣，于是將這種排序算法形象地稱為冒泡排序。

時間復雜度: 最佳 O(n) | 平均 O(n2) | 最差 O(n2)

空間復雜度: O(1)

穩定性:穩定（相等元素不交換）

二、應用場景/前提條件

適用于小規模數據
對幾乎已排序的數據效率較高

🌈 優點

代碼簡單，容易實現
適合小規模數據排序
對于幾乎已經排好序的數據，效率較高
穩定的排序算法

📢 缺點

時間復雜度高，為O(n2)
隨著元素數量增加，效率急劇下降
每次只能將一個元素移動到其最終位置，效率不高

三、經典算法實現并優化改進

相較于傳統的實現方法來說，有幾個可以優化的點，以下使用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(n2)
?最好時間復雜度?	O(n)
?平均時間復雜度?	O(n2)
?空間復雜度?	O(1)（原地排序）

?? ?說明?：盡管雙向遍歷優化了部分場景（如兩端元素有序時效率更高），但時間復雜度量級與傳統冒泡排序一致。

四、習題演練

2023下半年軟件設計師上午題——冒泡排序_冒泡排序選擇題

下面推薦一些可以用來練手的 LeetCode 題目：

75. 顏色分類?- 可使用冒泡排序解決，但有更優的解法
283. 移動零?- 可用冒泡排序的思想將零元素"冒泡"到數組末尾
912. 排序數組?- 可使用冒泡排序，但因為數據規模較大，可能會超時

需要注意的是，使用冒泡排序不一定是最優解，僅使用冒泡排序也可能無法解決問題，不過這些題目都能夠直接或間接體現冒泡排序核心思想，可以熟悉這個算法。

測驗

冒泡排序是穩定的排序算法嗎，為什么？
對于已經排好序的數組，優化版冒泡排序的時間復雜度是多少？
冒泡排序每一輪遍歷后，數組尾部會有什么特點？
如何優化冒泡排序以提高效率？

測驗答案

是的，冒泡排序是穩定的排序算法。因為只有當前一個元素大于后一個元素時才交換，相等元素不會改變相對位置。
對于已經排好序的數組，優化版冒泡排序的時間復雜度是O(n)。因為第一輪遍歷不會發生交換，優化版會檢測到這點并提前終止。
冒泡排序每一輪遍歷后，數組尾部會有一個元素到達其最終位置，且是當前未排序部分中的最大元素。第i輪結束后，末尾i個元素已排好序。
優化冒泡排序的方法:
添加標志位跟蹤是否發生交換，無交換則提前終止
記錄最后一次交換位置，下一輪只遍歷到該位置
使用雙向冒泡(雞尾酒排序)，同時將最大值上浮和最小值下沉