冒泡排序(冒泡法):算法原理,算法分析,時間複雜度,算法穩定性,算法描述,C語言,

冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序算法。

它重複地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果順序（如從大到小、首字母從Z到A）錯誤就把他們交換過來。走訪元素的工作是重複地進行直到沒有相鄰元素需要交換，也就是說該元素列已經排序完成。

這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。

基本介紹

中文名：冒泡排序
外文名：Bubble Sort
所屬學科：計算機科學
時間複雜度： O（n）
算法穩定性：穩定排序算法
實質：把小（大）的元素往前（後）調

算法原理,算法分析,時間複雜度,算法穩定性,算法描述,C語言,Visual Fox Pro語言,Python3,Swift,C++,RUBY,PHP,C#語言,Erlang,JAVA,Kotlin,JavaScript,Visual Basic語言,Objective-C,Go語言,GO語言2,PASCAL,Python,彙編,lua,最佳化,算法比較,插入排序,選擇排序,快速排序,歸併排序,

算法原理

冒泡排序算法的原理如下：

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

算法分析

時間複雜度

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

和記錄移動次數

均達到最小值：

，

。

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

。

若初始檔案是反序的，需要進行

趟排序。每趟排序要進行

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

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

。

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

。

算法穩定性

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

算法描述

C語言

#include <stdio.h>#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<len-1; i++) /* 外循環為排序趟數，len個數進行len-1趟 */        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;            }        }}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<len; i++)        printf ("%d\t", arr[i]);    putchar ('\n');        return 0;}

Visual Fox Pro語言

?'Original Array ' + CHR(43147)DIMENSION arr(10)FOR i = 1 TO 10    arr(i) = ROUND(rand()*100,0)ENDFORDISPLAY 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    ENDFORENDFORDISPLAY 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 numsprint(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 arrayend

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<Boftrue->[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 ; i<arr.length-1 ; i++) {                       for(int j=0 ; j<arr.length-1-i ; j++) {                  if(arr[j]>arr[j+1]) {                    int 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, 427)    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 iEnd 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 mainimport (    "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 bubbleListif __name__ == '__main__':    bubbleList = [3, 4, 1, 2, 5, 8, 0]    bubble(bubbleList)

彙編

有一個首地址為A的5個有符號數字的數組，請採用“冒泡”排序DATAS SEGMENTA  DW 9,4,26,85,38DATAS ENDSCODES SEGMENTASSUME CS:CODES,DS:DATASSTART:    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,字變數，下一個字偏移地址+2LOOP LP2  ;內循環次數-1,內循環次數是否為0？    DEC DI;外循環次數-1    JNZ LP1;外循環次數是否為0?    MOV AH,4CH    INT 21HCODES 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    endend

最佳化

針對問題：

數據的順序排好之後，冒泡算法仍然會繼續進行下一輪的比較，直到arr.length-1次，後面的比較沒有意義的。

方案：

設定標誌位flag，如果發生了交換flag設定為true；如果沒有交換就設定為false。

這樣當一輪比較結束後如果flag仍為false，即：這一輪沒有發生交換，說明數據的順序已經排好，沒有必要繼續進行下去。

以Java為例

public static void BubbleSort1(int [] arr){   int temp;//臨時變數　　   boolean flag;//是否交換的標誌　　   for(int i=0; i<arr.length-1; i++){   //表示趟數，一共 arr.length-1 次       // 每次遍歷標誌位都要先置為false，才能判斷後面的元素是否發生了交換　　       flag = false;　　       　　       for(int j=arr.length-1; j>i; j--){ //選出該趟排序的最大值往後移動           if(arr[j] < arr[j-1]){　　               temp = arr[j];　　               arr[j] = arr[j-1];　　               arr[j-1] = temp;　　               flag = true;    //只要有發生了交換，flag就置為true　　           }　　       }　　       // 判斷標誌位是否為false，如果為false，說明後面的元素已經有序，就直接return　　       if(!flag) break;　　   }　　}

算法比較

排序算法	平均時間複雜度
冒泡排序	O(n)
選擇排序	O(n)
插入排序	O(n)
希爾排序	O(n1.5)
快速排序	O(N*logN)
歸併排序	O(N*logN)
堆排序	O(N*logN)
基數排序	O(d(n+r))

插入排序

插入排序算法是基於某序列已經有序排列的情況下，通過一次插入一個元素的方式按照原有排序方式增加元素。這種比較是從該有序序列的最末端開始執行，即要插入序列中的元素最先和有序序列中最大的元素比較，若其大於該最大元素，則可直接插入最大元素的後面即可，否則再向前一位比較查找直至找到應該插入的位置為止。插入排序的基本思想是，每次將1個待排序的記錄按其關鍵字大小插入到前面已經排好序的子序列中，尋找最適當的位置，直至全部記錄插入完畢。執行過程中，若遇到和插入元素相等的位置，則將要插人的元素放在該相等元素的後面，因此插入該元素後並未改變原序列的前後順序。我們認為插入排序也是一種穩定的排序方法。插入排序分直接插入排序、折半插入排序和希爾排序3類。

選擇排序

選擇排序算法的基本思路是為每一個位置選擇當前最小的元素。選擇排序的基本思想是，基於直接選擇排序和堆排序這兩種基本的簡單排序方法。首先從第1個位置開始對全部元素進行選擇，選出全部元素中最小的給該位置，再對第2個位置進行選擇，在剩餘元素中選擇最小的給該位置即可；以此類推，重複進行“最小元素”的選擇，直至完成第(n-1)個位置的元素選擇，則第n個位置就只剩唯一的最大元素，此時不需再進行選擇。使用這種排序時，要注意其中一個不同於冒泡法的細節。舉例說明：序列58539．我們知道第一遍選擇第1個元素“5”會和元素“3”交換，那么原序列中的兩個相同元素“5”之間的前後相對順序就發生了改變。因此，我們說選擇排序不是穩定的排序算法，它在計算過程中會破壞穩定性。

快速排序

快速排序的基本思想是:通過一趟排序算法把所需要排序的序列的元素分割成兩大塊，其中，一部分的元素都要小於或等於另外一部分的序列元素，然後仍根據該種方法對劃分後的這兩塊序列的元素分別再次實行快速排序算法，排序實現的整個過程可以是遞歸的來進行調用，最終能夠實現將所需排序的無序序列元素變為一個有序的序列。

歸併排序

歸併排序算法就是把序列遞歸劃分成為一個個短序列，以其中只有1個元素的直接序列或者只有2個元素的序列作為短序列的遞歸出口，再將全部有序的短序列按照一定的規則進行排序為長序列。歸併排序融合了分治策略，即將含有n個記錄的初始序列中的每個記錄均視為長度為1的子序列，再將這n個子序列兩兩合併得到n/2個長度為2(當凡為奇數時會出現長度為l的情況)的有序子序列；將上述步驟重複操作，直至得到1個長度為n的有序長序列。需要注意的是，在進行元素比較和交換時，若兩個元素大小相等則不必刻意交換位置，因此該算法不會破壞序列的穩定性，即歸併排序也是穩定的排序算法。

冒泡排序