极客笔记Python中的冒泡排序
冒泡排序是各种排序算法中最简单的算法之一。我们将它作为第一个排序算法学习。它易于学习且直观性强。它可以很容易地实现到代码中，这对初学者软件开发人员非常有益。但是除非它每次都检查数组是否已排序，否则它是最糟糕的排序算法。
让我们理解冒泡排序的概念。
冒泡排序的概念
冒泡排序使用一种简单直观的逻辑，即如果相邻元素的顺序不正确，则重复交换它们。它一次比较一对元素，如果第一个元素大于第二个元素，则进行交换；否则，继续对下一对元素进行比较。
让我们通过一个示例来理解它 –
示例
我们正在创建一个存储整数数的元素列表
list1 = [5, 3, 8, 6, 7, 2]
在这里，算法对元素进行排序 –
第一次迭代
5, 3
它比较前两个元素，并且在这里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]
[3, 5, 6, 7, 2, 8] -> [3, 5, 6, 7, 2, 8]
[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, 2, 3,
检查每个元素，我们可以看到我们的列表使用冒泡排序技术已经排序。
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
所有的技术在少量元素时都是有用的，但是如果列表包含很多元素，那么第二个优化技术将会产生巨大的差异。