算法：冒泡排序算法

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

冒泡排序如何工作？

我们以一个未排序的数组为例。冒泡排序花费Ο(n 2)时间，因此我们保持简短和精确。

冒泡排序

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

冒泡排序

在这种情况下，值33大于14，因此它已经在已排序的位置。接下来，我们将33与27进行比较。

冒泡排序

我们发现27小于33并且必须交换这两个值。

冒泡排序

新数组应如下所示 -

冒泡排序

接下来我们比较33和35.我们发现两者都处于已排序的位置。

冒泡排序

然后我们转到接下来的两个值，35和10。

冒泡排序

我们当时知道10小了35.因此它们没有排序。

冒泡排序

我们交换这些值。我们发现我们已经到了数组的末尾。一次迭代后，数组应如下所示 -

冒泡排序

确切地说，我们现在展示了每次迭代后数组的外观。在第二次迭代之后，它应该看起来像这样 -

冒泡排序

请注意，在每次迭代后，最后至少有一个值移动。

冒泡排序

当不需要交换时，bubblesorts会知道数组是完全排序的。

冒泡排序

现在我们应该研究一下泡沫排序的一些实际方面。

算法

我们假设 list 是 n个元素的数组。我们进一步假设交换函数交换给定数组元素的值。

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

伪代码

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

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

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

履行

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

下一章：算法：插入排序算法

这是一种基于比较的就地排序算法。这里，维护一个始终排序的子列表。例如，维护数组的下半部分以进行排序。要在此已排序的子列表中“插入”的元素必须找到其适当的位置，然后必须将其插入其中。因此名称，插入排序。按顺序搜索数组，移 ...

上一章：算法：排序技术算法

下一章：算法：插入排序算法