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

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

冒泡排序的概念

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

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

示例 -

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

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   

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

标签: Tkinter教程, Tkinter安装, Tkinter库, Tkinter入门, Tkinter学习, Tkinter入门教程, Tkinter, Tkinter进阶, Tkinter指南, Tkinter学习指南, Tkinter进阶教程, Tkinter编程