排序算法是《數據結構與算法》中最基本的算法之一。排序算法可以分爲內部排序和外部排序,內部排序是數據記錄在內存中進行排序,而外部排序是因排序的數據很大,一次不能容納全部的排序記錄,在排序過程中需要訪問外存。常見的內部排序算法有:插入排序、希爾排序、選擇排序、冒泡排序、歸併排序、快速排序、堆排序、基數排序等。以下是冒泡排序算法:
冒泡排序(Bubble Sort)也是一種簡單直觀的排序算法。它重複地走訪過要排序的數列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換,也就是說該數列已經排序完成。這個算法的名字由來是因爲越小的元素會經由交換慢慢"浮"到數列的頂端。
作爲最簡單的排序算法之一,冒泡排序給我的感覺就像 Abandon 在單詞書裏出現的感覺一樣,每次都在第一頁第一位,所以最熟悉。冒泡排序還有一種優化算法,就是立一個 flag,當在一趟序列遍歷中元素沒有發生交換,則證明該序列已經有序。但這種改進對於提升性能來
說並沒有什麼太大作用。
1. 算法步驟 比較相鄰的元素。如果第一個比第二個大,就交換他們兩個。
對每一對相鄰元素作同樣的工作,從開始第一對到結尾的最後一對。這步做完後,最後的元素會是最大的數。
針對所有的元素重複以上的步驟,除了最後一個。
持續每次對越來越少的元素重複上面的步驟,直到沒有任何一對數字需要比較。
2. 動圖演示 3. 什麼時候最快 當輸入的數據已經是正序時(都已經是正序了,我還要你冒泡排序有何用啊)。
4. 什麼時候最慢 當輸入的數據是反序時(寫一個 for 循環反序輸出數據不就行了,幹嘛要用你冒泡排序呢,我是閒的嗎)。
5. JavaScript 代碼實現 實例 function bubbleSort
( arr
) { var len
= arr.
length ; for ( var i
= 0 ; i
< len
- 1 ; i
++ ) { for ( var j
= 0 ; j
< len
- 1 - i
; j
++ ) { if ( arr
[ j
] > arr
[ j
+ 1 ] ) { // 相鄰元素兩兩對比 var temp
= arr
[ j
+ 1 ] ; // 元素交換 arr
[ j
+ 1 ] = arr
[ j
] ; arr
[ j
] = temp
; } } } return arr
; } 6. Python 代碼實現 實例 def bubbleSort
( arr
) :
for i
in range ( 1 , len ( arr
) ) :
for j
in range ( 0 , len ( arr
) -i
) :
if arr
[ j
] > arr
[ j+
1 ] :
arr
[ j
] , arr
[ j +
1 ] = arr
[ j +
1 ] , arr
[ j
] return arr
7. Go 代碼實現 實例 func bubbleSort
( arr
[] int ) [] int { length
:= len ( arr
) for i := 0 ; i < length
; i ++ { for j
:= 0 ; j < length
- 1 - i ; j
++ { if arr
[ j
] > arr
[ j
+ 1 ] { arr
[ j
], arr
[ j
+ 1 ] = arr
[ j
+ 1 ], arr
[ j
] } } } return arr
} 8. Java 代碼實現 實例 public class BubbleSort
implements IArraySort
{ @Override
public int [ ] sort
( int [ ] sourceArray
) throws Exception { // 對 arr 進行拷貝,不改變參數內容 int [ ] arr
= Arrays .
copyOf ( sourceArray, sourceArray.
length ) ; for ( int i
= 1 ; i
< arr.
length ; i
++ ) { // 設定一個標記,若爲true,則表示此次循環沒有進行交換,也就是待排序列已經有序,排序已經完成。 boolean flag
= true ; for ( int j
= 0 ; j
< arr.
length - i
; j
++ ) { if ( arr
[ j
] > arr
[ j
+ 1 ] ) { int tmp
= arr
[ j
] ; arr
[ j
] = arr
[ j
+ 1 ] ; arr
[ j
+ 1 ] = tmp
; flag
= false ; } } if ( flag
) { break ; } } return arr
; } } 9. PHP 代碼實現 實例 function bubbleSort
( $arr ) { $len = count ( $arr ) ; for ( $i = 0 ; $i < $len - 1 ; $i ++ ) { for ( $j = 0 ; $j < $len - 1 - $i ; $j ++ ) { if ( $arr [ $j ] > $arr [ $j + 1 ] ) { $tmp = $arr [ $j ] ; $arr [ $j ] = $arr [ $j + 1 ] ; $arr [ $j + 1 ] = $tmp ; } } } return $arr ; } 10. C 語言 實例 #include <stdio.h> void bubble_sort
( int arr
[ ] , int len
) { int i
, j
, 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
[ ] = { 22 , 34 , 3 , 32 , 82 , 55 , 89 , 50 , 37 , 5 , 64 , 35 , 9 , 70 } ; int len
= ( int ) sizeof ( arr
) / sizeof ( * arr
) ; bubble_sort
( arr
, len
) ; int i
; for ( i
= 0 ; i
< len
; i
++ ) printf ( "%d " , arr
[ i
] ) ; return 0 ; } 11. C++ 語言 實例 #include <iostream> using namespace std
; template < typename T
> //整數或浮點數皆可使用,若要使用類(class)或結構體(struct)時必須重載大於(>)運算符 void bubble_sort
( T arr
[ ] ,
int len
) { int i, j
; for ( i
= 0 ; i
< len
- 1 ; i
++ ) for ( j
= 0 ; j
< len
- 1 - i
; j
++ ) if ( arr
[ j
] > arr
[ j
+ 1 ] ) swap
( arr
[ j
] , arr
[ j
+ 1 ] ) ; } 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
= ( float ) sizeof ( arrf
) / sizeof ( * arrf
) ; bubble_sort
( arrf, len
) ; for ( int i
= 0 ; i
< len
; i
++ ) cout << arrf
[ i
] << ' ' << endl
; return 0 ; } 12. C# 實例 static void BubbleSort
( int [ ] intArray
) { int temp
= 0 ; bool swapped
; for ( int i
= 0 ; i
< intArray
. Length ; i
++ ) { swapped
= false ; for ( int j
= 0 ; j
< intArray
. Length - 1 - i
; j
++ ) if ( intArray
[ j
] > intArray
[ j
+ 1 ] ) { temp
= intArray
[ j
] ; intArray
[ j
] = intArray
[ j
+ 1 ] ; intArray
[ j
+ 1 ] = temp
; if ( ! swapped
) swapped
= true ; } if ( ! swapped
) return ; } } 13. Ruby 實例 class Array def bubble_sort!
for i
in 0 ...
( size
- 1 ) for j
in 0 ...
( size
- i
- 1 ) self [ j
] ,
self [ j
+ 1 ] =
self [ j
+ 1 ] ,
self [ j
] if self [ j
] > self [ j
+ 1 ] end end self end end puts [ 22 ,
34 ,
3 ,
32 ,
82 ,
55 ,
89 ,
50 ,
37 ,
5 ,
64 ,
35 ,
9 ,
70 ] .
bubble_sort !
14. Swift 實例 import Foundation
func bubbleSort
( arr
: inout
[ Int
] ) { for i
in 0 ..<arr.count
- 1 { for j
in 0 ..<arr.count
- 1 - i
{ if arr
[ j
] > arr
[ j
+ 1 ] { arr.swapAt
( j, j
+ 1 ) } } } } // 測試調用 func testSort
( ) { // 生成隨機數數組進行排序操作 var list
: [ Int
] = [ ] for _
in 0 ...
99 { list.append
( Int
( arc4random_uniform
( 100 ) ) ) } print
( "( list)" ) bubbleSort
( arr
:& list
) print
( "( list)" ) } 原文地址:http s://github.com/hustcc/JS-Sorting-Algorithm/blob/master/1.bubbleSort.md
參考地址:https://zh.wikipedia.org/wiki/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F
以下是熱心網友對冒泡排序算法的補充,僅供參考:
熱心網友提供的補充1:
改進版冒泡排序
冒泡排序第1次遍歷後會將最大值放到最右邊,這個最大值也是全局最大值。標準冒泡排序的每一次遍歷都會比較全部的元素,雖然最右側的值已經是最大值了。改進之後,每次遍歷後的最大值,次大值,等等會固定在右側,避免了重複比較。
Python 實現:
def bubbleSort(arr): for i in range(len(arr) - 1, 0, -1): # 反向遍歷 for j in range(0, i): # 由於最右側的值已經有序,不再比較,每次都減少遍歷次數 if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr Go 實現:
func bubbleSort(arr []int) []int { for i := len(arr) - 1; i > 0;i-- { // 反向遍歷 for j := 0; j < i; j++ { if arr[j] > arr[j + 1]{ arr[j], arr[j + 1] = arr[j + 1], arr[j] } } } return arr} 熱心網友提供的補充2:
啦~~~只是多了一個哪裏已經有序的下表而已呀~~~性能提升了不少呢~~~
def bubble_sort(list): k = len(list) - 1 pos = 0 for i in range(len(list) - 1): flag = False for j in range(k): if list[j] > list[j + 1]: tmp = list[j] list[j] = list[j + 1] list[j + 1] = tmp flag = True pos = j k = pos if flag == False: break return listimport threadingfrom random import *from time import *class Thread(threading.Thread): def __init__(self,f): threading.Thread.__init__(self) self.input = None self.returnval = None self.f = f def run(self): if self.input != None: self.returnval = self.f(self.input) else: self.returnval = self.f() 再來開個多線程~~~順便加個條件纔開多線程~~~性能提升的不是一點點呢~~~
以上爲冒泡排序算法詳細介紹,插入排序、希爾排序、選擇排序、冒泡排序、歸併排序、快速排序、堆排序、基數排序等排序算法各有優缺點,用一張圖概括:
關於時間複雜度
平方階 (O(n2)) 排序 各類簡單排序:直接插入、直接選擇和冒泡排序。
線性對數階 (O(nlog2n)) 排序 快速排序、堆排序和歸併排序;
O(n1+§)) 排序,§ 是介於 0 和 1 之間的常數。 希爾排序
線性階 (O(n)) 排序 基數排序,此外還有桶、箱排序。
關於穩定性
穩定的排序算法:冒泡排序、插入排序、歸併排序和基數排序。
不是穩定的排序算法:選擇排序、快速排序、希爾排序、堆排序。
名詞解釋:
n:數據規模
k:"桶"的個數
In-place:佔用常數內存,不佔用額外內存
Out-place:佔用額外內存
穩定性:排序後 2 個相等鍵值的順序和排序之前它們的順序相同