氣泡排序演算法的理解
Understanding Bubble Sort Algorithm 氣泡排序法的原理是：在一個原本無序多個數字所組成的列表中，從頭開始將相鄰的數字逐一比較大小，如果是要由小至大排序，前面的數字若是大於後面的數字，則兩者須交換位置。如此相鄰繼續逐一比較下去，就可找到最大數字，無論有無發生交換，該數字最終會被排在最末端的位置。接下來，剛剛找到的最大數字以外的其它數字，再進行新一回的相鄰的數字逐一比較大小。一樣前面的數字若是大於後面的數字，則兩者須互相交換位置，如此相鄰逐一比較下去，就可找到次大的數字，且該數字會被排在倒數第二的位置。以此模式繼續多回比較，最後就可將列表中的數字由小至大排序。 如圖一所示，現在列表中有 5 個數字 {48, 24, 17, 20, 31} 要進行排序，若是採用氣泡排序法，因為相鄰的數字都要進行比較，則第一回要比較 4 次。此數目 4 其實就是這 5 個待排序數字的間隔數。 圖一 5 個數字排序， 第一回總共要比較 4 次 如圖二所示，這 5 個數字若是要由小至大排序，則相鄰數字在逐一比較 4 次後，就可找到最大值 48 ，且其經多次交換後就會被排至最末的位置。此時，只剩 4 個小於或等於 48 的數字需要進行新一回的比較。 圖二 第一回比較情形 圖三 第二回剩 4 個數字要排序，總共要比較 3 次 如圖四所示，第二回相鄰數字逐一比較 3 次後，就可找到次大的數字 31。接下來只剩 3 個數字尚未排序。而這剩下的 3 個數字，只須比較 2 次，就可以找到倒數第三大數字，如圖五所示。 圖四 第二回比較情形 圖五 第三回比較情形 最後一回只剩下兩個數字尚未排序，故只需一次比較，就完成整個列表數字的排序，如圖六所示。 圖六 第四回比較情形 下面以一程式示範氣泡排序法： C++ #include <iostream> using namespace std; int number[ ] = { 48, 24, 17, 20, 31 }; void bubble_sort(int x[ ]); int...
