冒泡算法-算法大全

{{noteTA
|G1=IT
|1=zh-tw:氣泡排序;zh-cn:冒泡排序;
}}

{{算法信息框
|class=[[排序算法]]
|image=[[File:Bubble sort animation.gif]]
|caption=使用冒泡排序為一列數字進行排序的過程
|data=[[數組]]
|best-time= $O(n)$
|average-time= $O(n^2)$
|time=$O(n^2)$
|space=总共$O(n)$，需要辅助空间$O(1)$
|optimal=No
}}
[[File:Bubblesort-edited-color.svg|frame|冒泡排序]]
”’冒泡排序”’（{{lang-en|”’Bubble Sort”’}}，台灣另外一種譯名為：”’泡沫排序”’）是一種簡單的[[排序算法]]。它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。

冒泡排序對$n$個項目需要[[大O符號|O]]($n^2$)的比較次數，且可以[[原地算法|原地]]排序。儘管這個演算法是最簡單瞭解和實作的排序算法之一，但它對於包含大量的元素的數列排序是很沒有效率的。

冒泡排序是與[[插入排序]]擁有相等的執行時間，但是兩種算法在需要的交換次數卻很大地不同。在最壞的情況，冒泡排序需要$O(n^2)$次交換，而插入排序只要最多$O(n)$交換。冒泡排序的實現（類似下面）通常會對已經排序好的數列拙劣地執行（$O(n^2)$），而插入排序在這個例子只需要$O(n)$個運算。因此很多現代的演算法教科書避免使用冒泡排序，而用插入排序取代之。冒泡排序如果能在內部迴圈第一次執行時，使用一個旗標來表示有無需要交換的可能，也可以把最壞情況下的複雜度降低到$O(n)$。在這個情況，已經排序好的數列就無交換的需要。若在每次走訪數列時，把走訪順序反過來，也可以稍微地改進效率。有時候稱為[[雞尾酒排序]]，因為演算法會從數列的一端到另一端之間穿梭往返。

冒泡排序演算法的運作如下：
# 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
# 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素會是最大的數。
# 針對所有的元素重複以上的步驟，除了最後一個。
# 持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。

由於它的簡潔，冒泡排序通常被用來對於程式設計入門的學生介紹演算法的概念。

== -{zh-hant:虛擬碼;zh-hans:伪代码}- ==

function bubble_sort (array, length) {
    var i, j;
    for(i from 0 to length-1){
        for(j from 0 to length-1-i){
            if (array[j] > array[j+1])
                swap(array[j], array[j+1])
        }
    }
}

-{zh-hant:
函數 冒泡排序 輸入 一個陣列名稱為array 其長度為length
    i 從 0 到 (length - 1)
        j 從 0 到 (length - 1 - i)
            如果 array[j] > array[j + 1]
                交換 array[j] 和 array[j + 1] 的值
            如果結束
        j迴圈結束
    i迴圈結束
函數結束
;zh-hans:
函数 冒泡排序 输入 一个数组名称为array 其长度为length 
    i 从 0 到 (length - 1) 
        j 从 0 到 (length - 1 - i) 
            如果 array[j] > array[j + 1] 
                交换 array[j] 和 array[j + 1] 的值 
            如果结束 
        j循环结束 
    i循环结束 
函数结束
}-

== 助记码 ==

i∈[0,N-1) //循环N-1遍
j∈[0,N-1-i) //每遍循环要处理的无序部分
swap(j,j+1) //两两排序（升序/降序）

[[File:冒泡排序.jpg]]

==實作範例==

===C语言===#include
void bubble_sort(int arr[], int len) {
int i, j, temp;
for (i = 0; i < len - 1; i++) for (j = 0; j < len - 1 - i; j++) if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = (int) sizeof(arr) / sizeof(*arr);
bubble_sort(arr, len);
int i;
for (i = 0; i < len; i++) printf("%d ", arr[i]); return 0; }

===C++===#include
#include
using namespace std;
template //整數或浮點數皆可使用,若要使用物件(class)時必須設定大於(>)的運算子功能
void bubble_sort(T arr[], int len) {
int i, j;
for (i = 0; i < len - 1; i++) for (j = 0; j < len - 1 - i; j++) if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
int main() {
int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
int len = (int) sizeof(arr) / sizeof(*arr);
bubble_sort(arr, len);
for (int i = 0; i < len; i++) cout << arr[i] << ' '; cout << endl; float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 }; len = (int) sizeof(arrf) / sizeof(*arrf); bubble_sort(arrf, len); for (int i = 0; i < len; i++) cout << arrf[i] << ' '; return 0; }

===C#===static void BubbleSort(int[] intArray) {
int temp = 0;
bool swapped;
for (int i = 0; i < intArray.Length; i++) { swapped = false; for (int j = 0; j < intArray.Length - 1 - i; j++) if (intArray[j] > intArray[j + 1])
{
temp = intArray[j];
intArray[j] = intArray[j + 1];
intArray[j + 1] = temp;
if (!swapped)
swapped = true;
}
if (!swapped)
return;
}
}

===JAVA===public static void bubbleSort(int[] arr) {
int i, j, temp, len = arr.length;
for (i = 0; i < len - 1; i++) for (j = 0; j < len - 1 - i; j++) if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}

===Ruby===class Array
def bubble_sort!
for i in 0…(size – 1)
for j in 0…(size – i – 1)
self[j], self[j + 1] = self[j + 1], self[j] if self[j] > self[j + 1]
end
end
self
end
end

puts [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70].bubble_sort!

===JavaScript===Array.prototype.bubble_sort = function() {
var i, j, temp;
for (i = 0; i < this.length - 1; i++) for (j = 0; j < this.length - 1 - i; j++) if (this[j] > this[j + 1]) {
temp = this[j];
this[j] = this[j + 1];
this[j + 1] = temp;
}
return this;
};
var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
num.bubble_sort();
for (var i = 0; i < num.length; i++) document.body.innerHTML += num[i] + " ";

===Pascal===
輸入：（在程式同目錄下的[[文本文件]]：input.txt）

　一行：等待排序的數（用空格隔開）；

　實例：194 638 124 482 469 245 852 294 484 243 623

輸出：（在程式同目錄下的文本文件：output.txt）

　一行：已經排好的數（從小到大）；

　實例：124 194 243 245 294 469 482 484 623 638 852procedure swap(j:longint); //交換過程
begin
a[j]:=a[j] xor a[j+1];
a[j+1]:=a[j] xor a[j+1];
a[j]:=a[j] xor a[j+1];
end;

procedure bubble_sort; //排序過程
var
i,j:longint;
flag:boolean; //flag標誌：若一次排序未發現數據交換，則說明數據已經有序，可以結束排序過程
begin
for i:=n-1 downto 1 do begin
flag:=true;
for j:=1 to i do begin
if a[j]>a[j+1] then begin
swap(j);
flag:=false;
end;
end;
if flag then exit;
end;
end;

===Python===def bubble(List):
for j in range(len(List)-1,0,-1):
flag = True
for i in range(0, j):
if List[i] > List[i+1]:
flag = False
List[i], List[i+1] = List[i+1], List[i]
if flag:
return List
return List

範例：testlist = [27, 33, 28, 4, 2, 26, 13, 35, 8, 14]
print(‘final:’, bubble(testlist))

輸出：
final: ([2, 4, 8, 13, 14, 26, 27, 28, 33, 35])

===VB.NET===

‘泡沫排序由大到小的程式，預先產生一儲存亂數內容的陣列B，使用中斷點check，
switch 為自定兩數交換的sub

Dim i, j, count As Integer

For i = 0 To UBound(b) – 1
Dim check As Boolean = False ‘進入排序後設定一布林變數令其初值為false

For j = 0 To UBound(b) – 1 – i
If b(j) < b(j + 1) Then switch(b(j), b(j + 1)) check = True '進行檢查程序，若符合交換條件即進行兩數值交換(呼叫sub程序) 並於交換後 '將check的值變更為true(表示有進行交換動作，則此數列尚未呈現最終排列序)， 離開本層for迴圈後再度將check值重設成false count += 1 Next If check = False Then Exit For '檢查進入迴圈後是否進行過數值交換，若check值為false， '則表示排序進行到此時所有數列的值已呈現期望中的順序， 因此尚未進行完的排序檢查動作可提早結束以提升效率。 Next MsgBox("共經過了" & count & "次排序") '泡沫排序由小到大的程式 Dim i, j, count As Integer Dim check As Boolean For i = 0 To UBound(b) - 1 check=false For j = 0 To UBound(b) - 1 - i If b(j) > b(j + 1) Then switch(b(j), b(j + 1))
count += 1
check = True
Next
If chk = False Then Exit For
Next

MsgBox(“共經過了” & count & “次的排序”)

‘兩數值交換程式
Private Sub switch(ByRef a as integer, ByRef b as integer)
Dim c As Integer
c = a
a = b
b = c
End Sub

===PHP===function swap(&$x, &$y) {
$t = $x;
$x = $y;
$y = $t;
}

function bubble_sort(&$arr) {//php的陣列視為基本型別，所以必須用傳參考才能修改原陣列
for ($i = 0; $i < count($arr) - 1; $i++) for ($j = 0; $j < count($arr) - 1 - $i; $j++) if ($arr[$j] > $arr[$j + 1])
swap($arr[$j], $arr[$j + 1]);
}

$arr = array(21, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70);
bubble_sort($arr);
for ($i = 0; $i < count($arr); $i++) echo $arr[$i] . ' ';

===Rust===fn bubble_sort(a: &mut [i32]) {
let mut i = 0;
let len = a.len();
while i < len - 1 { let mut j = 0; while j < len - i - 1 { if a[j] > a[j+1] {
let t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
j += 1;
}
i += 1;
}
}

调用：let mut a = [5,4,7,1,9];
bubble_sort(&mut a);
println!(“{:?}”, a);

===Go===// BubbleSort 冒泡排序. data必须实现sort包中的Interface接口
func BubbleSort(data sort.Interface) {
n := data.Len()
for i := 0; i < n-1; i++ { isChange := false for j := 0; j < n-1-i; j++ { if data.Less(j, j+1) { data.Swap(j, j+1) isChange = true } } if !isChange { break } } }
调用:// declare a array
// this array must implenet sort.Inerface
data := sort.IntSlice{22, 34, 3, 40, 18, 4}
BubbleSort(data)

==外部連結==
{{排序算法表}}
{{算法}}

[[Category:排序算法]]

[[no:Sorteringsalgoritme#Boblesortering]]