视频字幕
冒泡排序是一种简单直观的排序算法。它重复地遍历待排序的列表,比较相邻的两个元素,如果它们的顺序错误就把它们交换过来。这个算法的名字由来是因为越小的元素会慢慢"浮"到列表的顶端,就像水中的气泡一样。
冒泡排序的基本步骤如下:首先,从列表的第一个元素开始,比较它与紧邻的下一个元素。如果第一个元素比第二个元素大,则交换它们的位置。然后继续比较下一对相邻的元素,重复这个过程直到到达列表的末尾。经过一轮遍历,最大的元素会"冒泡"到列表的最后一个位置。接着对剩余未排序的部分重复上述过程,直到整个列表完全排序。
让我们通过一个例子来演示冒泡排序的过程。假设我们有一个初始数组[5, 3, 8, 4, 2]。在第一轮遍历后,最大的元素8会被移到最后,数组变成[3, 5, 4, 2, 8]。第二轮遍历后,次大的元素5会移到倒数第二位,数组变成[3, 4, 2, 5, 8]。第三轮遍历后,数组变成[3, 2, 4, 5, 8]。最后一轮遍历后,数组完全排序为[2, 3, 4, 5, 8]。这样,我们就完成了对数组的排序。
现在让我们看看冒泡排序的代码实现。在Python中,冒泡排序可以通过两层循环实现。外层循环控制排序的轮数,最多需要n-1轮,其中n是数组长度。内层循环负责比较相邻元素并在需要时交换它们。我们还可以添加一个优化:如果在某一轮遍历中没有发生任何交换,说明数组已经排序完成,可以提前退出循环。这个优化对于已经部分排序的数组特别有效。
最后,让我们分析冒泡排序的性能特点。冒泡排序的时间复杂度在最坏和平均情况下都是O(n²),其中n是数组长度。这是因为在最坏情况下,我们需要进行n-1轮排序,每轮需要比较n-i-1对元素。如果添加了提前退出的优化,在最好情况下(数组已经排序)时间复杂度可以降至O(n)。冒泡排序的空间复杂度是O(1),因为它只需要常数级的额外空间。冒泡排序是稳定的,相等元素的相对顺序在排序后不会改变。虽然冒泡排序不如快速排序等高级算法高效,但它实现简单,在数据量小或数据已经接近有序的情况下仍然有用。