冒泡排序(英语:Bubble Sort)又称为泡式排序,是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序对个项目需要O()的比较次数,且可以原地排序。尽管这个算法是最简单了解和实现的排序算法之一,但它对于包含大量的元素的数列排序是很没有效率的。

冒泡排序是与插入排序拥有相等的渐近时间复杂度,但是两种算法在需要的交换次数却很大地不同。在最坏的情况,冒泡排序需要次交换,而插入排序只要最多交换。冒泡排序的实现(类似下面)通常会对已经排序好的数列拙劣地执行(),而插入排序在这个例子只需要个运算。因此很多现代的算法教科书避免使用冒泡排序,而用插入排序取代之。冒泡排序如果能在内部循环第一次执行时,使用一个旗标来表示有无需要交换的可能,也可以把最优情况下的复杂度降低到。在这个情况,已经排序好的数列就无交换的需要。若在每次走访数列时,把走访顺序反过来,也可以稍微地改进效率。有时候称为鸡尾酒排序,因为算法会从数列的一端到另一端之间穿梭往返。

冒泡排序算法的运作如下:

  • 1.比较相邻的元素。如果第一个比第二个大,就交换它们两个。
  • 2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  • 3.针对所有的元素重复以上的步骤,除了最后一个。
  • 4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

由于它的简洁,冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。

伪代码

1
2
3
4
5
6
7
8
9
function bubble_sort (array, length) {
var i, j;
for(i from 0 to length-1){
for(j from 0 to length-2-i){
if (array[j] > array[j+1])
swap(array[j], array[j+1])
}
}
}
1
2
3
4
5
6
7
8
9
函数 冒泡排序 输入 一个数组名称为array 其长度为length
i 从 0 到 (length - 1)
j 从 0 到 (length - 2 - i)
如果 array[j] > array[j + 1]
交换 array[j] 和 array[j + 1] 的值
如果结束
j循环结束
i循环结束
函数结束

助记码

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

file

实现示例

C语言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>
#include <stdbool.h>

#define ARR_LEN 255 /* 數組長度上限 */
#define elemType int /* 元素類型 */

/* 泡沫排序 */
/* 1. 從當前元素起,向後依次比較每一對相鄰元素,若逆序則互換 */
/* 2. 對所有元素均重複以上步驟,直至最後一個元素 */
/* elemType arr[]: 排序目標數組; int len: 元素個數 */
void bubbleSort (int arr[], int len)
{

int i, j,temp;
_Bool exchanged = true;

for (i=0; exchanged && i<len-1; i++){ /* 外迴圈為排序趟數,len個數進行len-1趟,只有交換過,exchanged值為true才有必要執行迴圈,否則exchanged值為false不執行迴圈 */
exchanged = false;
for (j=0; j<len-1-i; j++)
{ /* 內迴圈為每趟比較的次數,第i趟比較len-i次 */
if (arr[j] > arr[j+1])
{ /* 相鄰元素比較,若逆序則互換(升序為左大於右,逆序反之) */
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
exchanged = true; /*只有數值互換過, exchanged才會從false變成true,否則數列已經排序完成,exchanged值仍然為false,沒必要排序 */
}
}
}
}

int main (void) {
int arr[ARR_LEN] = {3,5,1,-7,4,9,-6,8,10,4};
int len = 10;
int i;

bubbleSort (arr, len);

for (i=0; i<len; i++)
printf ("%d\t", arr[i]);
putchar ('\n');

return 0;
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
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 = (float) sizeof(arrf) / sizeof(*arrf);
bubble_sort(arrf, len);
for (int i = 0; i < len; i++)
cout << arrf[i] << ' '<<endl;
return 0;
}

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private int[] BubbleSort(int[] array)
{
var temp = 0;

for (int i = 0; i < array.Length; i++)
{
for (int j = 0; j < array.Length - 1 - i; j++)
{
if (array[j] > array[j + 1])
{
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}

return array;
}

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private int[] bubbleSort(int[] array) {
int temp;
for (int i = 0; i < array.length - 1; i++) {
boolean Flag = false; // 是否发生交换。没有交换,提前跳出外层循环
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
Flag = true;
}
}
if (!Flag)
{
break;
}
}
return array;
}

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 852

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
procedure 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

1
2
3
4
5
6
7
8
def bubble_sorted(iterable):
new_list = list(iterable)
list_len = len(new_list)
for i in range(list_len):
for j in range(list_len - i - 1):
if new_list[j] > new_list[j + 1]:
new_list[j], new_list[j + 1] = new_list[j + 1], new_list[j]
return new_list

范例:

1
2
testlist = [27, 33, 28, 4, 2, 26, 13, 35, 8, 14]
print('sorted:', bubble_sorted(testlist))

输出:

1
sorted: [2, 4, 8, 13, 14, 26, 27, 28, 33, 35]

Scratch

file

VB.NET

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
'泡沫排序由大到小的程式,預先產生一儲存亂數內容的陣列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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

1
2
3
4
5
6
7
8
9
pub fn bubble_sort(a: &mut[i32]){
for i in 0..a.len() {
for j in i..a.len() {
if a[i] > a[j] {
a.swap(i, j);
}
}
}
}

调用:

1
2
3
let mut a = [5,4,7,1,9];
bubble_sort(&mut a);
println!("{:?}", a);

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// BubbleSort 冒泡排序. data必须实现sort包中的Interface接口
func BubbleSort(data sort.Interface) {
n := data.Len()
for i := 0; i < n-1; i++ {
isChanged := false
for j := 0; j < n-1-i; j++ {
if data.Less(j, j+1) {
data.Swap(j, j+1)
isChanged = true
}
}
if !isChanged {
break
}
}
}

调用:

1
2
3
4
// declare a array
// this array must implenet sort.Inerface
data := sort.IntSlice{22, 34, 3, 40, 18, 4}
BubbleSort(data)

Objective-C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
- (NSArray*) bubbleSort: (NSArray *) unsortedArray {
if (unsortedArray.count <= 1) {
return unsortedArray;
}

NSMutableArray *sortedArray = [unsortedArray mutableCopy];

for (int i = 0; i < sortedArray.count-1; i++) {
BOOL exchanged = NO;
for (int j = 0; j< sortedArray.count-1-i; j++) {
if ([sortedArray[j] integerValue] > [sortedArray[j+1] integerValue]) {
[sortedArray exchangeObjectAtIndex:j withObjectAtIndex:j+1];
exchanged = YES;
}
}
if (!exchanged) {
break;
}
}

return [sortedArray copy];
}

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func bubbleSort(unsortedArray: inout [Int]){
guard unsortedArray.count > 1 else{
return
}

for i in 0 ..< unsortedArray.count-1 {
var exchanged = false
for j in 0 ..< unsortedArray.count-1-i {
if unsortedArray[j] > unsortedArray[j+1] {
unsortedArray.swapAt(j, j+1)
exchanged = true
}
}
if !exchanged {
break
}
}
}

// Test
var list = [2, 3, 5, 7, 4, 8, 6 ,10 ,1, 9]
print(list)
bubbleSort(unsortedArray: &list)
print(list)

Shell

1
2
3
4
5
6
7
8
9
10
11
12
13
#/bin/bash
read -p "Please enter a sequence: " -a num
for ((i=0;i<$[${#num[*]}-1];i++));do
for((j=0;j<$[$[${#num[*]}-1]-$i];j++));do
if [ ${num[$j]} -gt ${num[$[$j+1]]} ];then
A=${num[$j]}
num[$j]=${num[$[$j+1]]}
num[$[$j+1]]=$A

fi
done
done
echo ${num[*]}

IDL

1
2
3
4
5
6
7
8
9
10
FUNCTION BubbleSort, arr
FOR i = 0, N_ELEMENTS(arr) - 2 DO BEGIN
FOR j = i + 1, N_ELEMENTS(arr) - 1 DO BEGIN
IF arr[i] GT arr[j] THEN BEGIN
temp = arr[i] & arr[i] = arr[j] & arr[j] = temp
ENDIF
ENDFOR
ENDFOR
RETURN, arr
END

Julia (编程语言)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function BubbleSort(A)
n = length(A)
for i = 1:n
for j = 1:(n-i)
if(A[j]>A[j+1])
A[j+1],A[j] = A[j],A[j+1]
end
end
end
return A
end

# Main Code
A = [16,586,1,31,354,43,3]
print(A) # Original Array
print(BubbleSort(A)) # Bubble Sort Array

原文地址:https://zh.wikipedia.org/wiki/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F