冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序算法。
它重複地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果順序（如從大到小、首字母從Z到A） ...
反饋
分享
複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/冒泡排序/4602306
複製
複製成功
冒泡排序
編輯
鎖定
冒泡排序（BubbleSort），是一種計算機科學領域的較簡單的排序算法。
它重複地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果順序（如從大到小、首字母從Z到A）錯誤就把他們交換過來。
走訪元素的工作是重複地進行，直到沒有相鄰元素需要交換，也就是説該元素列已經排序完成。
這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。
中文名
冒泡排序
外文名
BubbleSort
所屬學科
計算機科學
時間複雜度
O（n²）
算法穩定性
穩定排序算法
實 質
把小（大）的元素往前（後）調
目錄
1
算法原理
2
算法分析
▪
時間複雜度
▪
算法穩定性
3
算法描述
▪
C語言
▪
VisualFoxPro語言
▪
Python3
▪
Swift
▪
C++
▪
RUBY
▪
PHP
▪
C#語言
▪
Erlang
▪
JAVA
▪
Kotlin
▪
JavaScript
▪
VisualBasic語言
▪
Objective-C
▪
Go語言
▪
GO語言2
▪
PASCAL
▪
Python
▪
彙編
▪
lua
4
優化
5
算法比較
▪
插入排序
▪
選擇排序
▪
快速排序
▪
歸併排序
冒泡排序算法原理
編輯
冒泡排序算法的原理如下：
[1]
比較相鄰的元素。
如果第一個比第二個大，就交換他們兩個。
[1]
對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最後一對。
在這一點，最後的元素應該會是最大的數。
[1]
針對所有的元素重複以上的步驟，除了最後一個。
[1]
持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。
[1]
冒泡排序流程圖
冒泡排序算法分析
編輯
冒泡排序時間複雜度
若文件的初始狀態是正序的，一趟掃描即可完成排序。
所需的關鍵字比較次數
和記錄移動次數
均達到最小值：
，
。
[1]
所以，冒泡排序最好的時間複雜度為
。
若初始文件是反序的，需要進行
趟排序。
每趟排序要進行
次關鍵字的比較(1≤i≤n-1)，且每次比較都必須移動記錄三次來達到交換記錄位置。
在這種情況下，比較和移動次數均達到最大值：
[1]
冒泡排序的最壞時間複雜度為
。
[1]
綜上，因此冒泡排序總的平均時間複雜度為
。
[1]
冒泡排序算法穩定性
冒泡排序就是把小的元素往前調或者把大的元素往後調。
比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。
所以，如果兩個元素相等，是不會再交換的；如果兩個相等的元素沒有相鄰，那麼即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前後順序並沒有改變，所以冒泡排序是一種穩定排序算法。
[1]
冒泡排序算法描述
編輯
冒泡排序C語言
#include
#define ARR_LEN 255 /*數組長度上限*/
#define elemType int /*元素類型*/
/* 冒泡排序 */
/* 1. 從當前元素起，向後依次比較每一對相鄰元素，若逆序則交換 */
/* 2. 對所有元素均重複以上步驟，直至最後一個元素 */
/* elemType arr[]: 排序目標數組; int len: 元素個數 */
void bubbleSort (elemType arr[], int len) {
elemType temp;
int i, j;
for (i=0; i arr[j+1]) { /* 相鄰元素比較，若逆序則交換（升序為左大於右，降序反之） */
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
int main (void) {
elemType 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 arr(j + 1)
lnTemp = arr(j)
arr(j) = arr(j + 1)
arr(j + 1) = lnTemp
ENDIF
ENDFOR
ENDFOR
DISPLAY MEMORY LIKE arr
冒泡排序Python3
def bubble_sort(nums):
for i in range(len(nums) - 1): # 這個循環負責設置冒泡排序進行的次數
for j in range(len(nums) - i - 1): # j為列表下標
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums
print(bubble_sort([45, 32, 8, 33, 12, 22, 19, 97]))
# 輸出：[8, 12, 19, 22, 32, 33, 45, 97]
冒泡排序Swift
func bubbleSort(_ nums: inout [Int]) {
let n = nums.count
for i in 0.. nums[j + 1] {
nums.swapAt(j, j + 1)
}
}
}
print(nums)
}
var nums = [1,3,7,8,9]
bubbleSort(&nums)
冒泡排序C++
C++語言程序示例如下#include
using namespace std;
template
//整數或浮點數皆可使用
void bubble_sort(T arr[], int len)
{
int i, j; T temp;
for (i = 0; i arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
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 = array[j + 1]
end
end
return array
end
冒泡排序PHP
function bubbleSort($numbers) {
$cnt = count($numbers);
for ($i = 0; $i $numbers[$j + 1]) {
$temp = $numbers[$j];
$numbers[$j] = $numbers[$j + 1];
$numbers[$j + 1] = $temp;
}
}
}
return $numbers;
}
$num = array(20, 40, 60, 80, 30, 70, 90, 10, 50, 0);
var_dump(bubbleSort($num));
//輸出結果如下：
//array(10) {
// [0]=>
// int(0)
// [1]=>
// int(10)
// [2]=>
// int(20)
// [3]=>
// int(30)
// [4]=>
// int(40)
// [5]=>
// int(50)
// [6]=>
// int(60)
// [7]=>
// int(70)
// [8]=>
// int(80)
// [9]=>
// int(90)
//}
冒泡排序C#語言
冒泡算法C#
namespace 數組排序
{
class Program
{
static void Main(string[] args)
{
int temp = 0;
int[] arr = {23, 44, 66, 76, 98, 11, 3, 9, 7};
#region該段與排序無關
Console.WriteLine("排序前的數組：");
foreach (int item in arr)
{
Console.Write(item + "");
}
Console.WriteLine();
#endregion
for (int i = 0; i arr[j + 1])
{
temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
#endregion
}
Console.WriteLine("排序後的數組：");
foreach (int item in arr)
{
Console.Write(item+"");
}
Console.WriteLine();
Console.ReadKey();
}
}
}
冒泡排序Erlang
bubble_sort(L)->
bubble_sort(L,length(L)).
bubble_sort(L,0)->
L;
bubble_sort(L,N)->
bubble_sort(do_bubble_sort(L),N-1).
do_bubble_sort([A])->
[A];
do_bubble_sort([A,B|R])->
caseA[A|do_bubble_sort([B|R])];
false->[B|do_bubble_sort([A|R])]
end.
冒泡排序JAVA
public static void bubbleSort(int arr[]) {
for(int i =0 ; iarr[j+1]) {
int temp = arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
冒泡排序Kotlin
fun bubbleSort(array: Array) {
val arrayLength = array.size
for (i in 0 until arrayLength) {
for (j in 0 until arrayLength - i - 1) {
if (array[j] > array[j + 1]) {
val temp = array[j]
array[j] = array[j + 1]
array[j + 1] = temp
}
}
}
// Prints result.
}
冒泡排序JavaScript
function bubbleSort(arr) {
var i = arr.length, j;
var tempExchangVal;
while (i > 0) {
for (j = 0; j arr[j + 1]) {
tempExchangVal = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tempExchangVal;
}
}
i--;
}
return arr;
}
var arr = [3, 2, 4, 9, 1, 5, 7, 6, 8];
var arrSorted = bubbleSort(arr);
console.log(arrSorted);
alert(arrSorted);
控制枱將輸出：[1,2,3,4,5,6,7,8,9]並且彈窗；
冒泡排序VisualBasic語言
Sub maopao()
Dim a = Array(233, 10086, 31, 15, 213, 5201314)
Dim i As Integer, j As Integer
For i = UBound(a) - 1 To 0 Step -1
For j = 0 To i
If a(j) > a(j + 1) Then
a(j) = a(j) + a(j + 1)
a(j + 1) = a(j) - a(j + 1)
a(j) = a(j) - a(j + 1)
End If
Next j
Next i
For i = 0 To UBound(a)
Print a(i)
Next i
End Sub
冒泡排序Objective-C
for (int i = 0; iright) {
[result exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
NSLog(@"%@",result);
冒泡排序Go語言
package main
import (
"fmt"
)
const (
LENGTH = 8
)
func main() {
var tmp int
number := []int{95, 45, 15, 78, 84, 51, 24, 12}
for i := 0; i i; j-- {
if number[j] values[j+1] {
values[j], values[j+1] = values[j+1], values[j]
flag = false
continue
}
}
if flag {
break
}
}
}
冒泡排序PASCAL
var
a:array[1..4] of integer;
i, j, temp, n:integer;
begin
read(n);
for i := 1 to n do read(a[i]);
for i := 1 to n do
for j := 1 to n-i do
if a[j] > a[j + 1] then
begin
temp := a[j];
a[j] := a[j + 1];
a[j+1] := temp;
end;
for i:= 1 to n do write(a[i]);
end.
冒泡排序Python
def bubble(bubbleList):
listLength = len(bubbleList)
while listLength > 0:
for i in range(listLength - 1):
if bubbleList[i] > bubbleList[i+1]:
bubbleList[i], bubbleList[i+1] = bubbleList[i+1], bubbleList[i]
listLength -= 1
print bubbleList
if __name__ == '__main__':
bubbleList = [3, 4, 1, 2, 5, 8, 0]
bubble(bubbleList)
冒泡排序彙編
有一個首地址為A的5個有符號數字的數組，請採用“冒泡”排序
DATAS SEGMENT
A DW 9,4,26,85,38
DATAS ENDS
CODES SEGMENT
ASSUME CS:CODES,DS:DATAS
START:
MOV AX,DATAS
MOV DS,AX
MOV DI,4;初始化外循環次數為數組個數-1
LP1:MOV CX,DI;外循環次數初值為數組個數-1
MOV BX,0;基址初值BX為0
LP2:MOV AX,A[BX]
CMP AX,A[BX+2]
JGE CONT;大於等於不交換
XCHG AX,A[BX+2];小於交換,AX保存的為較大的數
MOV A[BX],AX;A[BX]保存的為較大的數，準備進行下一次比較,
CONT:ADD BX,2;基址初值BX+2,字變量，下一個字偏移地址+2
LOOP LP2 ;內循環次數-1,內循環次數是否為0？
DEC DI;外循環次數-1
JNZ LP1;外循環次數是否為0?
MOV AH,4CH
INT 21H
CODES ENDS
END START
冒泡排序lua
function sortBubble(list)
local len = #list
for i = 1, len do
for j = 1, len-i do
if list[j+1]>list[j] then
local t = list[j+1]
list[j+1] = list[j]
list[j] = t
end
end
end
end
冒泡排序優化
編輯
針對問題：數據的順序排好之後，冒泡算法仍然會繼續進行下一輪的比較，直到arr.length-1次，後面的比較沒有意義的。
方案：設置標誌位flag，如果發生了交換flag設置為true；如果沒有交換就設置為false。
這樣當一輪比較結束後如果flag仍為false，即：這一輪沒有發生交換，説明數據的順序已經排好，沒有必要繼續進行下去。
以Java為例public static void BubbleSort1(int [] arr){
int temp;//臨時變量
boolean flag;//是否交換的標誌
for(int i=0; ii; j--){ //選出該趟排序的最大值往後移動
if(arr[j]
快速排序