Python 中的冒泡排序是什么？请举例说明？

冒泡排序是一种排序算法，用于将列表按升序（或降序）排序。这是最简单的排序算法，但效率不高。它可以用于较小的输入规模，但对于较长列表或数组来说，时间效率不高。其时间复杂度为 O(n^2)。然而，这是一种原地排序算法，这意味着它不使用任何额外的空间。因此，它在空间复杂度方面效率很高。但是，由于存在比冒泡排序更好的排序算法，因此它并没有被广泛使用。

冒泡排序是如何工作的？

在冒泡排序中，使用了两个 for 循环。外部 for 循环遍历列表。内部 for 循环也在外部循环的所有迭代中遍历列表。

冒泡排序中的主要操作是比较两个连续的元素。如果第一个元素大于下一个元素，则交换两者，以便较小的元素排在前面，较大的元素排在后面。在外部循环的一次迭代中，列表中最大的元素会到达最后一个索引。在外部循环的第二次迭代中，列表中第二大的元素会到达倒数第二个索引，依此类推。因此，在所有迭代结束时，我们得到了排序后的列表。

我们可以借助示例更好地理解。

示例

我们需要对以下列表进行排序。

外部循环=1

5>2，因此交换两者

5>1，因此交换两者

5>3，因此交换两者

5>4，因此交换两者

（在第一次外部迭代后，最大的元素 5 已到达最后一个索引）

外部循环=2

2>1，因此交换

不需要交换

不需要交换

我们可以看到，列表在第二次外部迭代中本身就被排序了。但是外部循环将再迭代 3 次，而无需进一步的交换操作。因此，示例中只显示了 2 次迭代。有时，列表本身可以在第一次迭代中被排序。有时，列表可能在最后一次迭代中被排序。因此，外部循环将始终迭代 n 次。

示例

 实时演示

def bubble_sort(arr):
   for i in range(len(arr)):
      for j in range(len(arr)-1):
         if(arr[j]>arr[j+1]):
            temp=arr[j]
            arr[j]=arr[j+1]
            arr[j+1]=temp
   return arr
array=[2,3,1,5,4]
print(bubble_sort(array))

输出

[1, 2, 3, 4, 5]

pawandeep

更新于： 2021-03-11

2K+ 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习