四、請詳述氣泡排序法（Bubble sort）、快速排序法（Quick sort）兩種排序方法，並比較何者平均時間較短？（15 分）

詳解 (共 1 筆)

詳解提供者：白龍@菜鳥公務員(107/10/29)

氣泡排序法（Bubble sort）:

由頭至尾每次比較相鄰兩項，如果後項>前項則互換，直到整體排序完成。

e.g. 25,33,15,3,42

25,15,3,33,42

15,3,25,33,42

3,15,25,33,42

快速排序法（Quick sort）:

選擇一基準值，將其他項與基準值相比分成大於、小於兩組，分別遞迴繼續排序。

e.g. 6,12,7,9,15,10,4,11 //黃色部分為基準值

4,6,7,9,15,10,12,11

4,6,7,9,15,10,12,11

4,6,7,9,15,10,12,11

4,6,7,9,11,10,12,15

4,6,7,9,10,11,12,15

4,6,7,9,10,11,12,15

時間複雜度:

氣泡排序法-平均: O(n²)

快速排序法-平均: O(nlogn)

平均時間較短者為快速排序法