反饋

冒泡排序

在程序設計語言中，排序算法主要有冒泡排序、快速排序、選擇排序以及計數排序等^[1] 。

冒泡排序（Bubble Sort）是最簡單和最通用的排序方法，其基本思想是：在待排序的一組數中，將相鄰的兩個數進行比較，若前面的數比後面的數大就交換兩數，否則不交換；如此下去，直至最終完成排序^[2] 。由此可得，在排序過程中，大的數據往下沉，小的數據往上浮，就像氣泡一樣，於是將這種排序算法形象地稱為冒泡排序^[3] 。

中文名: 冒泡排序
外文名: Bubble Sort
所屬學科: 計算機科學

時間複雜度: O（n²）
算法穩定性: 穩定排序算法
實質: 把小（大）的元素往前（後）調

冒泡排序算法原理

假定序列中有n個數，要進行從小到大的排序。若參與排序的數組元素共有n個，則需要輪排序。在第i輪排序中，從左端開始，相鄰兩數比較大小，若反序則將兩者交換位置，直到比較第個數為止。第1個數與第2個數比較，第2個數和第3個數比較，一直到第i個數與第個數比較，一共處理i次。此時，第個位置上的數已經有序，後續就不需要參加以後的排序。^[4]

（1）第1輪冒泡排序先從第1個數和第2個數開始比較，若第1個數大於第2個數，則需要交換兩者的位置；否則保持不變。重複這一過程，直到處理完本輪數列中最後兩個數。^[4]

（2）第2輪冒泡排序與第1輪冒泡排序進行相同的排序，使大的數交換到2的位置上。^[4]

（3）重複以上過程，共需經過輪冒泡排序後，數據實現升序排序。^[4]

冒泡排序算法示例

對於序列[26，28，24，11]，採用非遞減規則進行排序，排序過程如下所示。

冒泡排序實例圖

(1) 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。^[5]

(2) 對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。^[5]

(3) 針對所有的元素重複以上的步驟，除了最後一個。^[5]

(4) 持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。^[5]

冒泡排序算法分析

冒泡排序時間複雜度

若文件的初始狀態是正序的，一趟掃描即可完成排序。所需的關鍵字比較次數

和記錄移動次數

均達到最小值^[5] ：

，

。

所以，冒泡排序最好的時間複雜度為

。^[5]

若初始文件是反序的，需要進行

趟排序。每趟排序要進行

次關鍵字的比較(1≤i≤n-1)，且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下，比較和移動次數均達到最大值：^[5]

冒泡排序的最壞時間複雜度為

。^[5]

綜上，因此冒泡排序總的平均時間複雜度為

。^[5]

冒泡排序算法穩定性

冒泡排序就是把小的元素往前調或者把大的元素往後調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，是不會再交換的；如果兩個相等的元素沒有相鄰，那麼即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前後順序並沒有改變，所以冒泡排序是一種穩定排序算法。^[5]

冒泡排序算法實現

冒泡排序C語言

void bubble_sort(int* arr, int len)  
{  
    int i, j;  
    for (i = 0; i < len; i++)  
        for (j = 1; j < len - i; j++)  
            if (arr[j - 1] > arr[j])  
                swap(arr[j - 1], arr[j]);  
}

冒泡排序Visual Fox Pro語言

?'Original Array ' + CHR(43147)
DIMENSION arr(10)
FOR i = 1 TO 10
    arr(i) = ROUND(rand()*100,0)
ENDFOR
DISPLAY MEMORY LIKE arr
?'After Sort ' + CHR(43147)
FOR i = 1 TO 10
    FOR j = 1 TO 10 - i
        IF arr(j) > 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..<n {
        for j in 0..<(n - 1 - i) {
            if nums[j] > nums[j + 1] {
                nums.swapAt(j, j + 1)
            }
        }
    }
    print(nums)
}

var nums = [1,3,7,8,9]
bubbleSort(&nums)

冒泡排序C++

C++語言程序示例如下

#include <iostream>
using namespace std;
template<typename T>
//整數或浮點數皆可使用
void bubble_sort(T arr[], int len)
{
    int i, j;  T 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[] = { 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;
}

冒泡排序RUBY

def bubbleSort(array)
    return array if array.size < 2
    (array.size - 2).downto(0) do |i|
        (0 .. i).each do |j|
            array[j], array[j + 1] = array[j + 1], array[j] if array[j] >= array[j + 1]
        end
    end
    return array
end

冒泡排序PHP

function bubbleSort($numbers) {
    $cnt = count($numbers);
    for ($i = 0; $i < $cnt - 1; $i++) {
        for ($j = 0; $j < $cnt - $i - 1; $j++) {
            if ($numbers[$j] > $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.Length - 1; i++)
            {
                #region將大的數字移到數組的arr.Length-1-i
                for (int j = 0; j < arr.Length - 1 - i; j++)
                {
                    if (arr[j] > 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<Bof
true->[A|do_bubble_sort([B|R])];
false->[B|do_bubble_sort([A|R])]
end.

冒泡排序JAVA

    public static void bubbleSort(int arr[]) {
			   int temp;//臨時變量
        for(int i =0 ; i<arr.length-1 ; i++) { 
          
            for(int j=0 ; j<arr.length-1-i ; j++) {  

                if(arr[j]>arr[j+1]) {
                    temp = arr[j];
                    
                    arr[j]=arr[j+1];
                    
                    arr[j+1]=temp;
            }
            }    
        }
    }

冒泡排序Kotlin

fun bubbleSort(array: Array<Int>) { 
   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 < i - 1; j++) {
            if (arr[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]

並且彈窗；

冒泡排序Visual Basic語言

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; i<result.count-1; i++) {
        for (int j = 0; j<result.count-1-i; j++) {
            NSInteger left = [result[j] integerValue];
            NSInteger right = [result[j+1] integerValue];
            if (left>right) {
                [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 < LENGTH; i++ {
        for j := LENGTH - 1; j > i; j-- {
            if number[j] < number[j-1] {
                tmp = number[j-1]
                number[j-1] = number[j]
                number[j] = tmp
            }
        }
    }
    for i := 0; i < LENGTH; i++ {
        fmt.Printf("%d ", number[i])
    }
    fmt.Printf("\n")
}

冒泡排序GO語言2

func BubbleSort(values []int) {
    flag := true
    vLen := len(values)
    for i := 0; i < vLen-1; i++ {
        flag = true
        for j := 0; j < vLen-i-1; j++ {
            if values[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

冒泡排序算法改進

冒泡排序標誌法

對於序列[1，2，3，5，4]，在第1輪冒泡排序後，序列仍為[1，2，3，4，5]，進而發現後續3輪中都沒有發生數據交換，即其實不用再執行後面的幾輪。算法只需要執行到某輪排序不需要交換數據即可。^[4]

在原來的程序中，加上一個標誌變量flag，用於記錄在這一趟排序中是否發生了數交換。如果某輪結束後flag的值為False，則説明本輪沒有交換行為，數據已經全部有序，可以提前結束排序，具體如下。^[4]

（1）在第1輪冒泡排序中首先比較第1個數和第2個數，若前者大於後者，則交換兩者位置，同時flag=True；否則不換。重複這一過程，直到處理完最後兩個數據。^[4]

（2）如果flag=False，則結束循環；否則重複上述過程。

具體算法如下。^[4]

flag=True
for i in range(1,n):
flag=False
for j in range(0,n-i):
if a[j]<a[j+1]:
a[j],a[j+1]=a[j+1],a[j]
flag=True
if not flag:
break

冒泡排序區間控制法

對於序列[2，3，4，5，9，8，7]，採用“上冒”，並從數組的末尾開始進行排序，則第一輪排序結束後[2，3，4，5，7，9，8]。在第一趟排序中，當7和9交換位置後，後續的數字都沒有互換，即在後續的排序中[2，3，4，5]不需要參與排序。得出結論：每輪遍歷的區間邊界都是由上一輪遍歷最後一次發生交換的位置決定的。這樣一來，可以引入標記變量last記錄每輪排序最後一次交換的位置，並將last賦給下一輪遍歷區間的終點。大大縮小了下一輪排序遍歷區間，快速收縮待排序範圍，從而提高了算法效率。^[4]

例如，序列[2，3，4，5，9，8，7]，排序過程如下所示（“上冒”排序，並且從數組末尾開始比較）。

冒泡排序的排序區間分析圖

通過區間控制法，可以快速地結束排序。^[4]

（1）第1輪冒泡排序先比較第n-1個數和第n-2個數，若前者大於後者，則交換兩者位置，同時記錄最後一次交換的位置last，重複這一過程，直到處理完數組中最後兩個元素中的數據。^[4]

（2）下一輪排序從n-1至last，重複上面的過程，直到結束循環。^[4]

具體排序算法如下。^[4]

i=1
while i<n:
last=n-1
for j in range(n-1,i-1,-1):
if a[j]<a[j-1] :
a[j],a[j-1]=a[j-1],a[j]
last=j
i=last+1

冒泡排序算法比較

冒泡排序快速排序與冒泡排序

快速排序是對冒泡排序的一種改進。它的基本思想是，通過一趟排序將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。^[6]

一趟快速排序的具體做法是：假設兩個指針low和high設樞軸記錄的關鍵字為pivotkey，則首先從high所指位置起向前搜索找到第一個關鍵字小於pivotkey的記錄和樞軸記錄互相交換，然後從low所指位置起向後搜索，找到第一個關鍵字大於pivotkey的記錄和樞軸記錄互相交換，重複這兩步直至low=high為止。^[6]

快速排序示例圖

快速排序的平均時間為O(N*logN)，通常，快速排序被認為是，在所有同數量級O(N*logN)的排序方法中，其平均性能最好。但是，若初始記錄序列被關鍵字有序或基本有序時，快速排序將退化為冒泡排序，其時間複雜度為O(n²)。[9]

冒泡排序各種排序時間複雜度比較

排序算法比較圖

從平均時間性能而言，快速排序最佳，其所需時間最省，但快速排序在最壞情況下的時間性能不如堆排序和歸併排序。而後兩者相比較的結果是，在n較大時，歸併排序所需時間較堆排序省，但它所需的輔助存儲最多。[9]

從方法的穩定性來比較，基數排序是穩定的內排方法，直接插入排序和冒泡排序也是穩定的，然而，快速排序、堆排序和希爾排序等時間性能較好的排序方法都是不穩定的。一般來説，排序過程中的“比較”是在“相鄰的兩個記錄關鍵字”間進行的排序方法是穩定的。值得提出的是，穩定性是由方法本身決定的，對不穩定的排序方法而言，不管其描述形式如何，總能舉出一個説明不穩定的實例來。反之，對穩定的排序方法，總能找到一種不引起不穩定的描述形式。

參考資料

1. 楊波. 梁少林.C 語言中冒泡排序算法的教學設計與分析[J]. 信息與電腦，2015(16):180-181
2. 梁旭玲. C 語言排序算法的分析和總結[J]. 電腦知識與技術，2010,6(18):5041
3. 程妮.C語言中冒泡排序算法的教學設計與分析[J].現代計算機(專業版),2016(10):59-63
4. 胡偉東.冒泡排序算法的幾種優化與變形[J].電腦編程技巧與維護,2023(04):51-53.DOI:10.16184/j.cnki.comprg.2023.04.032
5. 呂新平、劉宏銘．二級公共基礎知識實戰訓練教程：西安交通大學出版社，2006
6. 嚴蔚敏、吳偉民．數據結構C語言版：清華大學出版社，2007

冒泡排序的概述圖（1張）

詞條統計

瀏覽次數：次
編輯次數：285次歷史版本
最近更新： Shirleysheep11 （2024-05-28）

冒泡排序

目錄

冒泡排序算法原理

冒泡排序算法示例

冒泡排序算法分析

冒泡排序時間複雜度

冒泡排序算法穩定性

冒泡排序算法實現

冒泡排序C語言

冒泡排序Visual Fox Pro語言

冒泡排序Python3

冒泡排序Swift

冒泡排序C++

冒泡排序RUBY

冒泡排序PHP

冒泡排序C#語言

冒泡排序Erlang

冒泡排序JAVA

冒泡排序Kotlin

冒泡排序JavaScript

冒泡排序Visual Basic語言

冒泡排序Objective-C

冒泡排序Go語言

冒泡排序GO語言2

冒泡排序PASCAL

冒泡排序Python

冒泡排序彙編

冒泡排序lua

冒泡排序算法改進

冒泡排序標誌法

冒泡排序區間控制法

冒泡排序算法比較

冒泡排序快速排序與冒泡排序

冒泡排序各種排序時間複雜度比較