Python教程-在Python中的冒泡排序

冒泡排序是各种排序算法中最简单的一种。我们通常将其作为第一个排序算法来学习。它易于理解，直观易懂，并且非常适合初学者的软件开发者。但是，除了检查数组是否已排序之外，它在排序元素方面是最差的算法。

让我们了解一下冒泡排序的概念。

冒泡排序的概念

冒泡排序使用一种简单的逻辑，即重复交换相邻元素，如果它们的顺序不正确。它一次比较一对元素，并在第一个元素大于第二个元素时进行交换，否则继续移动到下一对元素进行比较。

让我们通过一个示例来理解它 -

示例 -

我们创建一个存储整数数字的元素列表

list1 = [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]

第一次迭代完成，我们将最大的元素放在了最后。现在我们需要执行len(list1) - 1次迭代。

第二次迭代

[3, 5, 6, 7, 2, 8] - > [3, 5, 6, 7, 2, 8] here, 3<5 then no swap taken place

[3, 5, 6, 7, 2, 8] - > [3, 5, 6, 7, 2, 8] here, 5<6 then no swap taken place

[3, 5, 6, 7, 2, 8] - > [3, 5, 6, 7, 2, 8] here, 6<7 then no swap taken place

[3, 5, 6, 7, 2, 8] - > [3, 5, 6, 2, 7, 8] here 7>2 then swap their position. Now

[3, 5, 6, 2, 7, 8] - > [3, 5, 6, 2, 7, 8] here 7<8 then no swap taken place.

第三次迭代

[3, 5, 6, 2, 7, 8] - > [3, 5, 6, 7, 2, 8] here, 3<5 then no swap taken place

[3, 5, 6, 2, 7, 8] - > [3, 5, 6, 7, 2, 8] here, 5<6 then no swap taken place

[3, 5, 6, 2, 7, 8] - > [3, 5, 2, 6, 7, 8] here, 6<2 then swap their positions

[3, 5, 2, 6, 7, 8] - > [3, 5, 2, 6, 7, 8] here 6<7 then no swap taken place. Now

[3, 5, 2, 6, 7, 8] - > [3, 5, 2, 6, 7, 8] here 7<8 then swap their position.

它将一直迭代直到列表排序完成。

第四次迭代 -

[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()函数，它接受list1作为参数。

• 在函数内部，我们定义了两个for循环 - 第一个for循环遍历整个列表，第二个for循环遍历列表并比较每个外部循环迭代中的两个元素。
• 当它达到末尾时，for循环将终止。
• 在内部for循环中，我们定义了条件；如果第一个索引值大于第二个索引值，则交换它们的位置。
• 我们调用了该函数并传递了一个列表；它迭代并返回排序后的列表。

不使用临时变量

我们也可以在不使用临时变量的情况下交换元素。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   

所有这些技术对于元素较少的情况都是有用的，但如果列表包含许多元素，则第二种优化技术将产生巨大的差异。