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 

所有的技术对于较少的元素都是有用的，但是如果列表由许多元素组成，那么第二个优化技术会有很大的不同。