複製鏈接
請複製以下鏈接發送給好友

冒泡排序

鎖定
冒泡排序(Bubble Sort),是一種計算機科學領域的較簡單的排序算法
它重複地走訪過要排序的元素列,依次比較兩個相鄰的元素,如果順序(如從大到小、首字母從Z到A)錯誤就把他們交換過來。走訪元素的工作是重複地進行,直到沒有相鄰元素需要交換,也就是説該元素列已經排序完成。
這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端(升序或降序排列),就如同碳酸飲料二氧化碳的氣泡最終會上浮到頂端一樣,故名“冒泡排序”。
中文名
冒泡排序
外文名
Bubble Sort
所屬學科
計算機科學
時間複雜度
O(n²)
算法穩定性
穩定排序算法
實    質
把小(大)的元素往前(後)調

冒泡排序算法原理

冒泡排序算法的原理如下: [1] 
  1. 比較相鄰的元素。如果第一個比第二個大,就交換他們兩個。 [1] 
  2. 對每一對相鄰元素做同樣的工作,從開始第一對到結尾的最後一對。在這一點,最後的元素應該會是最大的數。 [1] 
  3. 針對所有的元素重複以上的步驟,除了最後一個。 [1] 
  4. 持續每次對越來越少的元素重複上面的步驟,直到沒有任何一對數字需要比較。 [1] 
冒泡排序流程圖 冒泡排序流程圖

冒泡排序算法分析

冒泡排序時間複雜度

若文件的初始狀態是正序的,一趟掃描即可完成排序。所需的關鍵字比較次數
和記錄移動次數
均達到最小值:
[1] 
所以,冒泡排序最好的時間複雜度
若初始文件是反序的,需要進行
趟排序。每趟排序要進行
次關鍵字的比較(1≤i≤n-1),且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下,比較和移動次數均達到最大值 [1] 
冒泡排序的最壞時間複雜度為
[1] 
綜上,因此冒泡排序總的平均時間複雜度為
[1] 

冒泡排序算法穩定性

冒泡排序就是把小的元素往前調或者把大的元素往後調。比較是相鄰的兩個元素比較,交換也發生在這兩個元素之間。所以,如果兩個元素相等,是不會再交換的;如果兩個相等的元素沒有相鄰,那麼即使通過前面的兩兩交換把兩個相鄰起來,這時候也不會交換,所以相同元素的前後順序並沒有改變,所以冒泡排序是一種穩定排序算法。 [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-1-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)
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

冒泡排序優化

  • 針對問題:
數據的順序排好之後,冒泡算法仍然會繼續進行下一輪的比較,直到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類。 [2] 

冒泡排序選擇排序

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

冒泡排序快速排序

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

冒泡排序歸併排序

歸併排序算法就是把序列遞歸劃分成為一個個短序列,以其中只有1個元素的直接序列或者只有2個元素的序列作為短序列的遞歸出口,再將全部有序的短序列按照一定的規則進行排序為長序列。歸併排序融合了分治策略,即將含有n個記錄的初始序列中的每個記錄均視為長度為1的子序列,再將這n個子序列兩兩合併得到n/2個長度為2(當凡為奇數時會出現長度為l的情況)的有序子序列;將上述步驟重複操作,直至得到1個長度為n的有序長序列。需要注意的是,在進行元素比較和交換時,若兩個元素大小相等則不必刻意交換位置,因此該算法不會破壞序列的穩定性,即歸併排序也是穩定的排序算法。 [2] 
參考資料
  • 1.    呂新平、劉宏銘.二級公共基礎知識實戰訓練教程:西安交通大學出版社,2006.02:30頁
  • 2.    李明達,何麗麗.論排序算法的效率[J]:中國管理信息化,2018:162-164
  • 3.    賈巧蘭.快速排序算法及其改進[J]:電腦迷,2018:226