冒泡排序

冒泡排序是不是简单，效率低下<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/sorting-algorithms/">排序算法用于排序<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/array">列表．它通常是计算机科学课程中最先教授的算法之一，因为它是学习建立排序直觉的好算法。虽然排序是一个简单的概念，但它是在复杂的计算机程序(如文件搜索、数据压缩和寻径)中使用的基本原理。在选择排序算法时，运行时间是需要考虑的一个重要因素，因为效率通常与速度有关。冒泡排序的平均运行时间和最坏情况运行时间为 $大(n ^ 2 O \ \大)$，所以在大多数情况下，更快的算法是更可取的。image1

映射下列输入/输出对的算法称为排序算法：

输入:一个数组, $一个$,包含 $n$公开元素:定货 $(0,1,…,n - 1)$．

的排序排列 $一个$,被称为 $B$,这样 $B[0] \leq B[1] \leq \cdots \leq B[n-1]。$

这是an的意思<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/arrays/">数组是排序．

一个数组 $< an >$是当且仅当对所有的 $i < j$， $ai \ leq a_j。$

换句话说，排序数组是按特定顺序排列的数组。例如, $(a, b, c, d)$是按照字母顺序排列的, $(1、2、3、4、5)$整数列表是否按递增顺序排序，和 $[5、4、3、2、1)$是按递减顺序排序的整数列表。

按照惯例，空数组和单例数组(只包含一个元素的数组)总是排序的。这是许多排序算法的基本情况的关键点。

冒泡排序算法比较数组中的每对元素，如果它们无序，则交换它们，直到整个数组排序完毕。对于列表中的每个元素，算法比较每对元素。

的冒泡排序算法如下:

1. 比较 $一个[0]$而且 $一个[1]$．如果 $一个[0]$比 $一个[1]$，交换元素。
2. 看下一个元素， $一个[1]$(现在可能包含来自上一步的交换的结果)，并将其与 $一个[2]$．如果 $一个[1]$比 $一个[2]$，交换元素。对每对元素执行此操作，直到列表结束。
3. 执行步骤1和2 $n$次了。

下面的动画演示了冒泡排序:

$} \水平间距{4厘米$image1

排序数组 $一个=[7、3、1、4、2)$使用冒泡排序算法。展示算法执行的所有步骤。

---

具体步骤总结如下表:

image2

下面是描述算法的伪代码:

1 2 3 4 5 6

2 for j = 1 to i-1 if a[j]>a[j+1] 4 swap(a[j]，a[j+1]);5如果

以下是代码的工作原理:

首先，它从 $j = 1$来 $j = n - 1$将列表中的每个元素与下一个元素进行比较 $\大($即 $文本(j + 1) ^ \ {th}$元素 $\大)。$如果 $j ^ \文本{th}$元素比下一个元素大，它们会改变位置，以此类推。这样，在第一次迭代中，具有最大值的元素将移到最后一个位置 $（$即去 $\ [N]}{)文本。$同样地，在循环的第二次迭代中， $j$从 $j = 1$来 $j = 2,$第二大的元素在最后一个元素之前的位置 $（$也就是说它会变成 $文本{\ [n]})。$程序一直执行这个过程，直到数组被排序。

上面的伪代码按递增顺序对列表进行排序。你要修改什么使你的程序按递减顺序排列元素?

---

您可以简单地更改伪代码的第三行:而不是使用 $文本\{“如果[j] > [j + 1],”}$你应该使用 $文本\{“如果[j] <} [j + 1]”。$ $_ \广场$

下面是在Python中实现冒泡排序的一种方法。还有其他实现算法的方法，但所有实现都源于相同的思想。冒泡排序可用于对任何可排序列表进行排序。

1 2 3 4 5 6 7 8

defbubble_sort（数组)：指数＝len（数组）-1而指数> =0：为j在范围（指数)：如果数组［j］>数组［j+1]:数组［j),数组［j+1］＝数组［j+1),数组［j］指数- =1返回数组

为了计算冒泡排序算法的复杂度，确定每个循环执行多少次比较是很有用的。对于数组中的每个元素，冒泡排序是这样做的 $n - 1$比较。在<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/big-o-notation/">大魔神符号，执行冒泡排序 $O (n)$比较。因为数组包含 $n$元素，它有一个 $O (n)$元素的数量。换句话说，执行冒泡排序 $O (n)$操作在一个 $O (n)$元素的数量，导致总运行时间为 $大(n ^ 2 O \ \大)$．

另一种分析冒泡排序复杂性的方法是确定<一个target="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/recurrence-relations/">递归式表示它的关系。

当 $我= 1,$程序不进行比较。当 $我= 2,$程序进行了一个比较。当 $我= 3,$进行两次比较，以此类推。因此，我们可以得出结论:当 $i = m,$ $m - 1$比较。因此，在长度数组中 $n,$它 $1 + 2 + 3 + 4 + \ cdots + (2) + (n - 1)$比较。

请注意, $\sum_{q=1}^{p} q= \frac{p(p+1)}{2}。$用前面的公式计算 $1 + 2 + 3 + 4 + \ cdots + (2) + (n - 1),$由此可见, $\压裂{(n - 1) (n + 1)}{2} = \压裂{n (n - 1)}{2}。$使用<一个href="//www.parkandroid.com/wiki/master-theorem/" class="wiki_link" title="主定理" target="_blank">主定理求出运行时间的递归式。不出所料，算法的复杂度为 $大(n ^ 2 O \ \大)。$

注意: $O (n)$是冒泡排序的最佳运行时间。可以修改冒泡排序来跟踪它执行的交换数。如果数组已经排序，且冒泡排序不进行交换，则算法可以在经过一次之后终止。通过这种修改，如果冒泡排序遇到一个已经排序的列表，它将在中结束 $O (n)$时间。

虽然冒泡排序方法简单，易于实现，但由于其运行时间较慢，很难解决大多数问题。它的平均运行时间和最坏情况运行时间为 $大(n ^ 2 O \ \大)$，且只能在其最佳情况下运行时运行 $O (n)$当输入列表已经排序时。

冒泡排序是一种稳定排序<一个href="//www.parkandroid.com/wiki/space-complexity/" class="wiki_link" title="空间复杂度" target="_blank">空间复杂度的 $O (1)$．