氣泡排序法
基本概念
- 比較相鄰元素：從數列的第最後一個元素開始，依次比較相鄰的兩個元素。
- 交換位置：如果前一個元素大於後一個元素，則交換這兩個元素的位置。
- 重複過程：對整個數列進行多次遍歷，每次遍歷都將最大的元素移至末尾。
- 結束條件：當一輪遍歷中沒有進行任何交換時，表示數列已經排好序，可以停止排序。
排序過程示例
假設有一串數字：
- 第一輪：
比對，不需移動，保持不變。 比對，交換，變為 。 比對，交換，變為 。 比對，交換，變為 。 - 第一輪結果:
- 第二輪：
比對，交換，變為 。 比對，交換，變為 。 比對，交換，變為 。 比對，不需移動，保持不變。 - 第二輪結果:
- 第三輪：
比對，不需移動，保持不變。 比對，交換，變為 。 - 繼續比對，但都不需交換 最終答案：
程式碼範例
Problem H Bubble sort，計算swaps次數
python
for _ in range(int(input())):
n = int(input())
ary = list(map(int, input().split()))
count = 0
for i in range(len(ary)):
for j in range(i, len(ary)):
if ary[i] > ary[j]:
ary[i], ary[j] = ary[j], ary[i]
count += 1
print(f'Optimal train swapping takes {count} swaps.')TA001 排序練習 氣泡排序法
python
import sys
for line in sys.stdin.read().splitlines():
nums = list(map(int, line.split(", ")))
n = len(nums)
for i in range(n - 1):
for j in range(n - i - 1):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
if i == 1:
break
print(nums)特點
時間複雜度：
- 最佳情況：
，當數列已經排好序時。 - 最壞情況：
，當數列完全逆序時。 - 平均情況：
。
- 最佳情況：
空間複雜度：
，因為它是一種原地排序演算法，不需要額外的存儲空間。 穩定性：氣泡排序是一種穩定的排序演算法，相同值的元素在排序後相對位置不會改變。
Contributors
lucashsu95