基本介紹
- 中文名：冒泡排序
- 外文名：Bubble Sort
- 所屬學科：計算機科學
- 時間複雜度： O（n2）
- 算法穩定性：穩定排序算法
- 實質：把小（大）的元素往前（後）調
算法原理,算法分析,時間複雜度,算法穩定性,算法描述,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 =1;i<arr.length;i++) { for(int j=0;j<arr.length-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
