logo图片
数据结构与算法

冒泡排序

冒泡排序是一种简单的排序算法。这种排序算法是基于比较的算法,其中每对相邻元素进行比较,如果元素不按顺序进行交换。该算法不适用于大型数据集,因为它的平均复杂度和最坏情况复杂度为 Ο(n 2),其中 n 是项目数。

冒泡排序如何工作?

我们以一个未排序的数组为例。冒泡排序需要 Ο(n 2) 时间,所以我们保持它的简短和精确。
冒泡排序
冒泡排序从前两个元素开始,比较它们以检查哪个更大。
冒泡排序
在这种情况下,值 33 大于 14,因此它已经在排序位置。接下来,我们将 33 与 27 进行比较。
冒泡排序
我们发现27小于33,这两个值必须交换。
冒泡排序
新数组应该是这样的-
冒泡排序
接下来我们比较 33 和 35、我们发现两者都在已经排序的位置。
冒泡排序
然后我们转到接下来的两个值,35 和 10、
冒泡排序
我们知道 10 小于 35、因此它们没有排序。
冒泡排序
我们交换这些值。我们发现我们已经到了数组的末尾。一次迭代后,数组应如下所示-
冒泡排序
确切地说,我们现在展示的是数组在每次迭代后的样子。在第二次迭代之后,它应该是这样的-
冒泡排序
请注意,在每次迭代之后,至少有一个值在最后移动。
冒泡排序
当不需要交换时,冒泡排序会得知数组已完全排序。
冒泡排序
现在我们应该研究冒泡排序的一些实际方面。

算法

我们假设 listn 个元素的数组。我们进一步假设 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

实施

我们在原始算法及其临时伪代码中没有解决的另一个问题是,在每次迭代之后,最高值会在数组末尾稳定下来。因此,下一次迭代不需要包括已经排序的元素。为此,在我们的实现中,我们限制内部循环以避免已经排序的值。
昵称: 邮箱:
Copyright © 2020 立地货 All Rights Reserved.
备案号:京ICP备14037608号-4