数据结构 - 冒泡排序算法

冒泡排序是一种简单的排序算法.该排序算法是基于比较的算法，其中比较每对相邻元素，并且如果元素不按顺序则交换元素.该算法不适用于大数据集，因为它的平均和最差情况复杂度为Ο(n ² )其中 n 是项目数.

冒泡排序的工作原理是什么？

我们为示例采用未排序的数组.冒泡排序采用Ο(n ² )时间，因此我们保持简短和精确.

冒泡排序从前两个元素开始，比较它们以检查哪一个更大.

在这种情况下，值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

Pseudocode

我们在算法中观察到Bubble Sort比较每对数组元素，除非整个数组按升序完全排序.这可能会导致一些复杂性问题，例如，如果所有元素都已经提升，那么数组不再需要交换.

为了缓解问题，我们使用一个标志变量交换这将帮助我们查看是否发生了任何交换.如果没有发生交换，即数组不再需要进行排序处理，它就会退出循环.

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

实现

我们在原始算法及其即兴伪代码中未解决的另一个问题是，在每次迭代后，最高值在数组末尾处稳定下来.因此，下一次迭代不需要包括已经排序的元素.为此，在我们的实现中，我们限制内部循环以避免已经排序的值.

要了解C编程语言中的冒泡排序实现.