例如五個數字原本由左至右為 ④, ⑤, ②, ③, ①
想要將它由左至右~ 變成從小到大的順序~
由 ④ 開始，將其依序與它左邊的 ⑤, ②, ③, ① 比大小，
如果發現對方比較小就交換位置~
④, ⑤, ②, ③, ①
└──┘
第一次比較： 沒有比較小，不換
④, ⑤, ②, ③, ①
└────┘
第二次比較： 有比較小，交換，變成 ②, ⑤, ④, ③, ①
②, ⑤, ④, ③, ①
└───────┘
第三次比較： 沒有比較小，不換
②, ⑤, ④, ③, ①
└─────────┘
第四次比較： 有比較小，交換，變成 ①, ⑤, ④, ③, ②
經過四次比較，可以挑出最小的放在最左邊，
①, ⑤, ④, ③, ②
^^^^^^^^^^^^^^還沒有挑選的
同上述程序，可以 "再" 經由三次比較挑出 ⑤, ④, ③, ② 中最小的，
放在這四個數字的最左邊，變成 ①, ②, ⑤, ④, ③
^^^^^^^^^^還沒有挑選的
餘同理。
因此，五個數字的泡泡排序法，須經過 4+3+2+1 = 4*(4+1)/2 次比較，完成排序。
因此， n 個數字的泡泡排序法，須經過 (n-1)+(n-2)+(n-3)+....+2+1 = (n-1)*[(n-1)+1]/2 次比較，完成排序。
|