一亮靴、算法簡介
冒泡排序（Bubble Sort）是一種計(jì)算機(jī)科學(xué)最簡單的排序算法之一宴树。
它通過重復(fù)地走訪要排序的數(shù)列藐握，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過來褥芒。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換嚼松，也就是說該數(shù)列已經(jīng)完成排序。
1. 算法原理
冒泡排序算法的動作原理如下：（從后往前）
- 比較相鄰的元素锰扶。如果前面的元素比第二個(gè)大献酗，那么就交換他們兩個(gè)。
- 對每一對相鄰元素作同樣的工作坷牛，從開始第一對到結(jié)尾的最后一對罕偎。這樣每循環(huán)一次，最大的數(shù)都會移到最后面京闰。
- 針對所有的元素重復(fù)以上步驟颜及，除最后一個(gè)元素外。
- 持續(xù)每次對越來越少的元素重復(fù)上面的步驟蹂楣，直到?jīng)]有任何一對數(shù)字需要比較器予。
2. 算法分析
2.1 時(shí)間復(fù)雜度
- 最好：初始狀態(tài)為正序
當(dāng)數(shù)列的初始狀態(tài)為正序時(shí)，所需的關(guān)鍵字比較次數(shù)$C$和記錄移動次數(shù)$M$均達(dá)到最小值：$C_{min}=n-1,M_{min}=0$捐迫，此時(shí)，時(shí)間復(fù)雜度為$O(n)$爱葵。
- 最壞：初始狀態(tài)為逆序
當(dāng)數(shù)列的初始狀態(tài)是反序時(shí)施戴，需要進(jìn)行$n-1$趟排序。每趟排序要進(jìn)行$n-i$次關(guān)鍵字的比較($1≤i≤n-1$)萌丈，且每次比較都必須移動記錄三次來達(dá)到交換記錄位置赞哗。在這種情況下，比較和移動次數(shù)均達(dá)到最大值：
$$
C_{max}=\frac{n(n-1)}{2}=O(n^2)
$$
$$
M_{max}=\frac{3n(n-1)}{2}=O(n^2)
$$
冒泡排序的最壞時(shí)間復(fù)雜度為$O(n^2)$辆雾。
綜上肪笋，因此冒泡排序的平均時(shí)間復(fù)雜度為$O(n^2)$。
2.2 空間復(fù)雜度
冒泡排序的空間復(fù)雜度取決于交換兩個(gè)元素位置所采用的算法。
| 算法過程 | 優(yōu)缺點(diǎn) | 空間復(fù)雜度 |
|---|---|---|
| temp=a;a=b;b=a; | 消耗空間 | $O(1)$ |
| a=a+b;b=a-b;a=a-b; | 可能會造成越界 | $O(0)$ |
| a=a*b;b=a/b;a=a/b; | 可能會造成越界 | $O(0)$ |
| a=a^b;b=a^b;a=a^b; | 邏輯較復(fù)雜 | $O(0)$ |
2.3 穩(wěn)定性
冒泡排序就是把小的元素向前移或把大的元素向后移藤乙，比較的是兩個(gè)相鄰的元素猜揪，交換也是發(fā)生在這兩個(gè)元素之間。所以坛梁，如果兩個(gè)元素相等而姐，不需要進(jìn)行交換；如果兩個(gè)元素沒有相鄰划咐，那么即使通過前面的兩兩交換氫兩個(gè)相鄰起來拴念，這時(shí)候也不會交換，所以相同元素的前后順序并沒有改變褐缠，所以冒泡排序是一種穩(wěn)定的排序算法政鼠。
3. 偽代碼
BUBBLE-SORT(A){
swapped
for(i = A.length downto 1){
swapped = false
for(j = 1 to i ){
if(A[j+1]>A[j]){
temp = A[j]
A[j] = A[j+1]
A[j+1] = temp
break = true
}
}
if(!swapped) break
}
}
4. 算法流程
二、算法實(shí)現(xiàn)
1. Kotlin
/**
* 冒泡排序
* 1. 外層循環(huán)：需要遍歷的元素個(gè)數(shù)
* 2. 內(nèi)層循環(huán)：比較相鄰元素的大小
* @author likly
* @version 1.0
*/
/**
* 冒泡排序
* @param array 要排序的數(shù)組
* @param debug 是否輸入調(diào)試信息
*/
fun bubbleSort(array: Array<Int>,debug:Boolean = false){
var swapped = false
for(i in array.size-1 downTo 1){
swapped = false
for(j in 0 until i){
if(array[j+1] < array[j]){
val temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
swapped = true
}
if(debug){
printlnArray("第${array.size -i}*${j+1}次冒泡",array = array)
}
}
if(!swapped) break
}
}
fun main(args: Array<String>) {
val array = arrayOf(4,6,5,2,3,1)
printlnArray("排序前",array)
bubbleSort(array,true)
printlnArray("排序后",array)
}
