Python 中的冒泡排序

冒泡排序是各種排序算法中的一種簡單算法。我們把它作為第一種排序算法來學習。它易學，直觀性強。它可以很容易地實現到代碼中，這對初學者軟件開發人員非常有利。但它是排序每個中的元素的最差算法，因為它會在每次數組排序或不排序時進行檢查。

讓我們理解冒泡排序的概念。

冒泡排序的概念

冒泡排序使用一種簡單的邏輯，如果相鄰元素的順序不對，就重複交換相鄰元素。它一次比較一對，如果第一個元素大於第二個元素，則交換；否則，進一步移動到下一對元素進行比較。

讓我們通過一個例子來理解它-

示例-

我們正在創建一個存儲整數的元素列表

列表 1 = [5，3，8，6，7，2]

這裡算法排序元素-

第一次迭代

[5, 3, 8, 6, 7, 2]

它比較前兩個元素，這裡 5>3，然後互相交換。現在我們得到的新名單是-

[ 3，5， 8，6，7，2]

在第二次比較中，5 < 8，然後交換髮生-

[3、 5、8、 6、7、2]

在第三個比較中，8>6，然後交換-

[3，5， 6，8， 7，2]

在第四次比較中，8>7，然後交換-

[3，5，6， 7，8 ，2]

在第五次比較中，8>2 然後交換-

[3，5，6，7， 2，8 ]

在這裡，第一次迭代完成了，最後我們得到了最大的元素。現在我們需要鏡頭(列表 1) – 1

第二次迭代

[ 3、5 ，6、7、2、8] – > [ 3、5 ，6、7、2、8]這裡，3 < 5 則沒有發生交換

[3、 5、6、 7、2、8] – > [3、 5、6、 7、2、8]這裡，5 < 6 則沒有發生交換

[3，5， 6，7 ，2，8]->【3，5， 6，7 ，2，8】這裡，6 < 7 則沒有發生交換

【3、5、6、 7、2 、8】->【3、5、6、 2、7 、8】這裡 7 > 2 然後互換位置。現在

[3、5、6、 2、7 、8] – > [3、5、6、2、 7、8 ]此處為 7 < 8，則無交換髮生。

第三次迭代

[ 3、5 ，6、2、7、8] – > [ 3、5 ，6、7、2、8]這裡，3 < 5 則沒有發生交換

[3、 5、6、 2、7、8] – > [3、 5、6、 7、2、8]這裡，5 < 6 則沒有發生交換

【3、5、 6、2 、7、8】->【3、5、 2、6 、7、8】這裡，6 < 2 然後互換位置

[3、5、2、 6、7 、8] – > [3、5、2、 6、7 、8]此處為 6 < 7，則無交換髮生。現在

【3、5、2、6、 7、8->【3、5、2、6、 7、8 這裡 7 < 8 然後互換位置。

它將迭代直到列表被排序。

第四次迭代-

【 3、5 ，2、6、7、8】->【3、5、 2、6、7、8】

[3 、5、2 、6、7、8] – > [3、 2、5 、6、7、8]

[3，2， 5，6 ，7，8] – > [3，2， 5，6 ，7，8]

【3、2、5、 6、7 、8】->【3、2、5、 6、7 、8】

【3、2、5、 6、7 、8】->【3、2、5、 6、7 、8】

第五次迭代

[3, 2, 5, 6, 7, 8] – > [2, 3, 5, 6, 7, 8]

檢查每個元素，我們可以看到我們的列表是使用冒泡排序技術排序的。

Python 代碼中的實現

我們已經描述了氣泡分類技術。現在，我們將在 Python 代碼中實現該邏輯。

程序

# Creating a bubble sort function
def bubble_sort(list1):
    # Outer loop for traverse the entire list
    for i in range(0,len(list1)-1):
        for j in range(len(list1)-1):
            if(list1[j]>list1[j+1]):
                temp = list1[j]
                list1[j] = list1[j+1]
                list1[j+1] = temp
    return list1

list1 = [5, 3, 8, 6, 7, 2]
print("The unsorted list is: ", list1)
# Calling the bubble sort function
print("The sorted list is: ", bubble_sort(list1))

輸出:

The unsorted list is:  [5, 3, 8, 6, 7, 2]
The sorted list is:  [2, 3, 5, 6, 7, 8]

說明:

在上面的代碼中，我們定義了一個 bubble_sort() 函數，該函數以列表 1 為參數。

• 在函數內部，我們定義了兩個 for循環-第一個 for循環迭代完整的列表，第二個 for循環迭代列表，並在每次外部循環迭代中比較兩個元素。
• 當 for循環到達末尾時，它將被終止。
• 我們已經在內部 for循環中定義了條件；如果第一個索引值大於第二個索引值，則互相交換它們的位置。
• 我們調用了函數並傳遞了一個列表；它迭代並返回排序列表。

不使用臨時變量

我們也可以在不使用 temp 變量的情況下交換元素。Python 有一個非常獨特的語法。我們可以使用下面幾行代碼。

示例-

def bubble_sort(list1):
    # Outer loop for traverse the entire list
    for i in range(0,len(list1)-1):
        for j in range(len(list1)-1):
            if(list1[j]>list1[j+1]): 
                # here we are not using temp variable
                list1[j],list1[j+1] = list1[j+1], list1[j]
    return list1

list1 = [5, 3, 8, 6, 7, 2]
print("The unsorted list is: ", list1)
# Calling the bubble sort function
print("The sorted list is: ", bubble_sort(list1))

輸出:

The unsorted list is:  [5, 3, 8, 6, 7, 2]
The sorted list is:  [2, 3, 5, 6, 7, 8]

Python 代碼實現的優化

我們可以使用這兩種技術優化上面的代碼。互換沒有完成；這意味着列表已排序。在前面的技術中-前面的技術將評估完整的列表，儘管它似乎沒有必要這樣做。

我們可以使用布爾標誌來防止不必要的評估，並檢查在前一節中是否進行了任何交換。

示例-

def bubble_sort(list1):
   # We can stop the iteration once the swap has done
    has_swapped = True

    while(has_swapped):
        has_swapped = False
        for i in range(len(list1) - 1):
            if list1[i] > list1[i+1]:
                # Swap
                list1[i], list1[i+1] = list1[i+1], list1[i]
                has_swapped = True
    return list1

list1 = [5, 3, 8, 6, 7, 2]
print("The unsorted list is: ", list1)
# Calling the bubble sort function
print("The sorted list is: ", bubble_sort(list1))

輸出:

The unsorted list is:  [5, 3, 8, 6, 7, 2]
The sorted list is:  [2, 3, 5, 6, 7, 8]

在第二種技術中，我們考慮這樣一個事實:當列表中最大的元素在列表的末尾結束時，迭代就結束了。

第一次，我們使用 n 位置在結束位置傳遞最大的元素。第二次，我們通過第二大元素 n-1 位置。

在每次連續迭代中，我們可以比以前少比較一個元素。更準確地說，在第 k 次迭代中，只需要比較第 n – k + 1 個元素:

示例-

def bubble_sort(list1):
    has_swapped = True

    total_iteration = 0

    while(has_swapped):
        has_swapped = False
        for i in range(len(list1) - total_iteration - 1):
            if list1[i] > list1[i+1]:
                # Swap
                list1[i], list1[i+1] = list1[i+1], list1[i]
                has_swapped = True
        total_iteration += 1
    print("The number of iteraton: ",total_iteration)
    return list1

list1 = [5, 3, 8, 6, 7, 2]
print("The unsorted list is: ", list1)
# Calling the bubble sort funtion
print("The sorted list is: ", bubble_sort(list1))

輸出:

The unsorted list is:  [5, 3, 8, 6, 7, 2]
The number of iteraton:  6
The sorted list is:  [2, 3, 5, 6, 7, 8]

時間比較

讓我們看看上面代碼片段之間的時間比較。

Unoptimized Bubble Sort Takes: 0.0106407
Optimize Bubble Sort Takes: 0.0078251
Bubble Sort with a Boolean flag and shortened list Takes: 0.0075207 

所有的技術對於較少的元素都是有用的，但是如果列表由許多元素組成，那麼第二個優化技術會有很大的不同。