-
冒泡排序
鎖定
冒泡排序(Bubble Sort),是一種計算機科學領域的較簡單的排序算法。
它重複地走訪過要排序的元素列,依次比較兩個相鄰的元素,如果順序(如從大到小、首字母從Z到A)錯誤就把他們交換過來。走訪元素的工作是重複地進行,直到沒有相鄰元素需要交換,也就是説該元素列已經排序完成。
- 中文名
- 冒泡排序
- 外文名
- Bubble Sort
- 所屬學科
- 計算機科學
- 時間複雜度
- O(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-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]