Python 中的氣泡排序是什麼？請舉例說明？

氣泡排序是一種排序演算法，用於將列表按升序（或降序）排序。這是最簡單的排序演算法，但效率不高。它可以用於較小的輸入規模，但對於較長列表或陣列來說，時間效率不高。其時間複雜度為 O(n^2)。然而，這是一種原地排序演算法，這意味著它不使用任何額外的空間。因此，它在空間複雜度方面效率很高。但是，由於存在比氣泡排序更好的排序演算法，因此它並沒有被廣泛使用。

氣泡排序是如何工作的？

在氣泡排序中，使用了兩個 for 迴圈。外部 for 迴圈遍歷列表。內部 for 迴圈也在外部迴圈的所有迭代中遍歷列表。

氣泡排序中的主要操作是比較兩個連續的元素。如果第一個元素大於下一個元素，則交換兩者，以便較小的元素排在前面，較大的元素排在後面。在外部迴圈的一次迭代中，列表中最大的元素會到達最後一個索引。在外部迴圈的第二次迭代中，列表中第二大的元素會到達倒數第二個索引，依此類推。因此，在所有迭代結束時，我們得到了排序後的列表。

我們可以藉助示例更好地理解。

示例

我們需要對以下列表進行排序。

外部迴圈=1

5>2，因此交換兩者

5>1，因此交換兩者

5>3，因此交換兩者

5>4，因此交換兩者

（在第一次外部迭代後，最大的元素 5 已到達最後一個索引）

外部迴圈=2

2>1，因此交換

不需要交換

不需要交換

我們可以看到，列表在第二次外部迭代中本身就被排序了。但是外部迴圈將再迭代 3 次，而無需進一步的交換操作。因此，示例中只顯示了 2 次迭代。有時，列表本身可以在第一次迭代中被排序。有時，列表可能在最後一次迭代中被排序。因此，外部迴圈將始終迭代 n 次。

示例

 即時演示

def bubble_sort(arr):
   for i in range(len(arr)):
      for j in range(len(arr)-1):
         if(arr[j]>arr[j+1]):
            temp=arr[j]
            arr[j]=arr[j+1]
            arr[j+1]=temp
   return arr
array=[2,3,1,5,4]
print(bubble_sort(array))

輸出

[1, 2, 3, 4, 5]

pawandeep

更新於： 2021-03-11

2K+ 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習