冒泡排序
冒泡排序是一种简单的排序算法。这种排序算法是基于比较的算法,其中每对相邻元素进行比较,如果元素不按顺序进行交换。该算法不适用于大型数据集,因为它的平均复杂度和最坏情况复杂度为 Ο(n
2),其中
n 是项目数。
冒泡排序如何工作?
我们以一个未排序的数组为例。冒泡排序需要 Ο(n
2) 时间,所以我们保持它的简短和精确。
冒泡排序从前两个元素开始,比较它们以检查哪个更大。
在这种情况下,值 33 大于 14,因此它已经在排序位置。接下来,我们将 33 与 27 进行比较。
我们发现27小于33,这两个值必须交换。
新数组应该是这样的-
接下来我们比较 33 和 35、我们发现两者都在已经排序的位置。
然后我们转到接下来的两个值,35 和 10、
我们知道 10 小于 35、因此它们没有排序。
我们交换这些值。我们发现我们已经到了数组的末尾。一次迭代后,数组应如下所示-
确切地说,我们现在展示的是数组在每次迭代后的样子。在第二次迭代之后,它应该是这样的-
请注意,在每次迭代之后,至少有一个值在最后移动。
当不需要交换时,冒泡排序会得知数组已完全排序。
现在我们应该研究冒泡排序的一些实际方面。
算法
我们假设
list 是
n 个元素的数组。我们进一步假设
swap 函数交换给定数组元素的值。
begin BubbleSort(list)
for all elements of list
if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for
return list
end BubbleSort
伪代码
我们在算法中观察到冒泡排序会比较每一对数组元素,除非整个数组完全按升序排序。这可能会导致一些复杂性问题,例如如果数组不再需要交换,因为所有元素都已经升序了。
为了缓解这个问题,我们使用一个标志变量
swapped 来帮助我们查看是否发生了任何交换。如果没有发生交换,即数组不需要更多的处理来排序,它将退出循环。
BubbleSort算法的伪代码可以写成如下-
procedure bubbleSort( list : array of items )
loop = list.count;
for i = 0 to loop-1 do:
swapped = false
for j = 0 to loop-1 do:
/* compare the adjacent elements */
if list[j] > list[j+1] then
/* swap them */
swap( list[j], list[j+1] )
swapped = true
end if
end for
/*if no number was swapped that means
array is sorted now, break the loop.*/
if(not swapped) then
break
end if
end for
end procedure return list
实施
我们在原始算法及其临时伪代码中没有解决的另一个问题是,在每次迭代之后,最高值会在数组末尾稳定下来。因此,下一次迭代不需要包括已经排序的元素。为此,在我们的实现中,我们限制内部循环以避免已经排序的值。