NO IMAGE

Bubble Sort比較簡單,本文首先列出了基礎版本Bubble Sort的虛擬碼,之後做兩點小的優化。

1.基礎版本BubbleSort

# 原始版的BubbleSort
# 時間複雜度為O(n^2)
function BubbleSort(array X[], int length) 
for (int i = 0;  i < length; i  ) 
for (int j = 0; j < length - 1 - i; j  ) 
if (X[j] > X[j 1])
swap(X[j], X[j 1];

2.優化-有序停止

# 如果幾個交換後序列已經有序,則停止。
# 即在本次迴圈中,沒有發生元素交換,則已經有序。
function BubbleSort(array X[], int length) 
int isSorted = true;
for (int = 0; i < length; i  )
isSorted = true;
for (int j = 0; j < length - 1 - i; j  )
if (X[j] > X[j 1])
swap(X[j], X[j 1]);
isSorted = false;
# 未發生過元素交換,已經有序。
if (isSorted == true)
break;

3.優化-後半部有序,減少比較次數

# 如果元素後半部分已經有序,則會進行多次無意義的比較。
function BubbleSort(array X[], int length) 
int isSorted = true;
int lastChangeIndex = 0;
int sortedBorder = length - 1;
for (int i = 0; i < length; i  )
isSorted = true;
for (int j = 0; j < SortedBorder; j  )
if (X[j] > X[j 1])
swap(X[j],X[j 1]);
isSorted = false;
lastChangeIndex = j;
sortedBorder = lastChangeIndex;
if (isSorted == true)
break;

參考自:https://mp.weixin.qq.com/s/05TUWmBcq4ZoX3o0EEk38w