算 法：冒泡排序算法
時間復雜度：
- 冒泡排序算法概述
- 冒泡排序偽代碼
- 冒泡排序?qū)崿F(xiàn)
冒泡排序算法概述
冒泡排序通常是我們在學習編程的過程中遇到排序問題哨鸭，最先接觸到的算法，它的算法過程就是每一趟排序都會通過交換不滿足排序狀態(tài)的相鄰兩個數(shù)來達到每一趟排序都讓一個元素“冒泡”到正確位置像鸡，直到最后一趟“冒泡”過程完成，也就完成了排序哈恰。
冒泡排序算法描述
- 第
趟“冒泡”過程從序列尾部遍歷至第
- 對于每一趟“冒泡”過程只估，比較每個正在遍歷的元素與前一個元素的大小關系，如不滿足着绷，則交換2者位置;
- 持續(xù)1-2步驟直至對于每個位置都進行一趟“冒泡”過程為止蛔钙。
冒泡排序示例
未排序： 5 31 16 7 9 10 3
第一趟： [3] 5 31 16 7 9 10
第二趟： [3 5] 7 31 16 9 10
第三趟： [3 5 7] 9 31 16 10
第四趟： [3 5 7 9] 10 31 16
第五趟： [3 5 7 9 10] 16 31
第六趟： [3 5 7 9 10 16] 31
第七趟： [3 5 7 9 10 16 31]
冒泡排序偽代碼
（引用自《算法導論》）
BUBBLESORT(A)
for i = 1 to A.length - 1
for j = A.length downto i + 1
if A[j] < A[j - 1]
exchange A[j] with A[j - 1]
冒泡排序?qū)崿F(xiàn)
C
void bubbleSort(arrType* a, int arrLength)
{
int i, j, t;
for (i = 0; i < arrLength - 1; i++) {
for (j = arrLength - 1; j > i; j--) {
if (a[j] < a[j - 1]) {
t = a[j];
a[j] = a[j - 1];
a[j - 1] = t;
}
}
}
}
Pascal
procedure bubblesort;
var
i, j, t : integer;
begin
for i := 1 to arrLength - 1 do
for j := arrLength downto i + 1 do
if a[j] < a[j - 1] then
begin
t := a[j];
a[j] := a[j - 1];
a[j - 1] := t;
end;
end;
參考資料
- 《算法導論》（第三版）
本文首發(fā)于個人博客算法 - 冒泡排序 | 不存在的貓， 轉(zhuǎn)載請注明出處
