Data Structures Algorithms 简明教程

Bubble Sort Algorithm

冒泡排序是一种简单的排序算法。该排序算法是基于比较的算法，其中比较相邻的两对元素，如果不按顺序则交换这些元素。此算法不适用于大型数据集，因为其平均和最坏情况的复杂度为 O(n2)，其中 n 是项目的数量。

Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order. This algorithm is not suitable for large data sets as its average and worst case complexity are of O(n2) where n is the number of items.

Bubble Sort Algorithm

冒泡排序是一种基本排序算法，通过根据需要重复交换相邻元素来工作。当不需要交换时，文件将被排序。

Bubble Sort is an elementary sorting algorithm, which works by repeatedly exchanging adjacent elements, if necessary. When no exchanges are required, the file is sorted.

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

We assume list is an array of n elements. We further assume that swap function swaps the values of the given array elements.

*第 1 步 *——检查输入数组中的第一个元素是否大于数组中的下一个元素。

*Step 1 *− Check if the first element in the input array is greater than the next element in the array.

*第 2 步 *——如果较大，则交换这两个元素；否则，在数组中向前移动指针。

*Step 2 *− If it is greater, swap the two elements; otherwise move the pointer forward in the array.

步骤 3−重复步骤 2，直至达到数组末尾。

*Step 3 *− Repeat Step 2 until we reach the end of the array.

步骤 4−检查元素是否已排序；如果没有，则从数组的最后一个元素到第一个元素重复上述过程（步骤 1 至步骤 3）。

*Step 4 *− Check if the elements are sorted; if not, repeat the same process (Step 1 to Step 3) from the last element of the array to the first.

步骤 5−最终获得的结果是有序数组。

*Step 5 *− The final output achieved is the sorted array.

Algorithm: Sequential-Bubble-Sort (A)
fori ← 1 to length [A] do
for j ← length [A] down-to i +1 do
   if A[A] < A[j-1] then
      Exchange A[j] ⟷ A[j-1]

Pseudocode

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

We observe in algorithm that Bubble Sort compares each pair of array element unless the whole array is completely sorted in an ascending order. This may cause a few complexity issues like what if the array needs no more swapping as all the elements are already ascending.

为了简化此问题，我们使用一个标记变量 swapped ，该变量将帮助我们了解是否发生过任何交换。如果没有发生交换，即数组不再需要进一步处理即可排序，它将退出循环。

To ease-out the issue, we use one flag variable swapped which will help us see if any swap has happened or not. If no swap has occurred, i.e. the array requires no more processing to be sorted, it will come out of the loop.

冒泡排序算法的伪代码可以写成如下：

Pseudocode of bubble sort algorithm can be written as follows −

voidbubbleSort(int numbers[], intarray_size){
   inti, j, temp;
   for (i = (array_size - 1); i>= 0; i--)
   for (j = 1; j <= i; j++)
   if (numbers[j-1] > numbers[j]){
      temp = numbers[j-1];
      numbers[j-1] = numbers[j];
      numbers[j] = temp;
   }
}

Analysis

在此处，比较次数是

Here, the number of comparisons are

       1 + 2 + 3 + ... + (n - 1) = n(n - 1)/2 = O(n2)

很明显，该图显示了冒泡排序的 n2 特性。

Clearly, the graph shows the n2 nature of the bubble sort.

在此算法中，比较次数与数据集无关，即提供的输入元素是按升序、降序或随机顺序排列的。

In this algorithm, the number of comparison is irrespective of the data set, i.e. whether the provided input elements are in sorted order or in reverse order or at random.

Memory Requirement

从上述算法可以清楚看出，冒泡排序不需要额外的内存。

From the algorithm stated above, it is clear that bubble sort does not require extra memory.

Example

我们以一个未排序数组为例。冒泡排序耗费 Ο(n2) 时间，所以我们将其简短而精炼。

We take an unsorted array for our example. Bubble sort takes Ο(n2) time so we’re keeping it short and precise.

Bubble sort

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

Bubble sort starts with very first two elements, comparing them to check which one is greater.

first two elements

在此情况下，值 33 大于 14，所以它已经位于经过排序的位置。接着，我们将 33 与 27 比较。

In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we compare 33 with 27.

sorted locations

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

We find that 27 is smaller than 33 and these two values must be swapped.

swapped

接着，我们比较 33 和 35。我们发现这两者都位于经过排序的位置。

Next we compare 33 and 35. We find that both are in already sorted positions.

sorted positions

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

Then we move to the next two values, 35 and 10.

two values

我们知道 10 小于 35。因此，它们未经排序。我们将这些值交换。我们发现已经达到数组末尾。经过一次迭代后，数组应如下所示−

We know then that 10 is smaller 35. Hence they are not sorted. We swap these values. We find that we have reached the end of the array. After one iteration, the array should look like this −

10 smaller 35

确切地说，我们现在展示了每个迭代之后数组应如何显示。经过第二次迭代后，它应如下所示−

To be precise, we are now showing how an array should look like after each iteration. After the second iteration, it should look like this −

iteration
second iteration

请注意，在每次迭代后，至少有一个值会移动到末尾。

Notice that after each iteration, at least one value moves at the end.

value moves end
iteration 27
iteration 10
iteration 0

并且当不需要交换时，冒泡排序会认为数组是完全排序的。

And when there’s no swap required, bubble sort learns that an array is completely sorted.

array completely sorted

现在我们应该深入了解冒泡排序的某些实用方面。

Now we should look into some practical aspects of bubble sort.

Implementation

在原来的算法和修改过的伪代码中，我们尚未解决另一个问题，那就是每次迭代后，最高值都会驻留在数组的末尾。因此，下一个迭代不必包含已排序的元素。为此，在我们的实现中，我们将内循环限制在避免已排序的值内。

One more issue we did not address in our original algorithm and its improvised pseudocode, is that, after every iteration the highest values settles down at the end of the array. Hence, the next iteration need not include already sorted elements. For this purpose, in our implementation, we restrict the inner loop to avoid already sorted values.