Articles

冒泡排序(Bubble Sort)

Introduction to Algorithms 这本书习题2-2中提到了冒泡排序。

BUBBLESORT(A)
  for i = 1 to A.length - 1
    for j = A.length downto i + 1
      if A[j] < A[j - 1]
        exchange A[j] with A[j - 1]

The Algorithm Design Manual 这本书习题1-9也提到了冒泡排序。

function bubblesort (A : list[1 . . . n])
  var int i, j
  for i from n to 1
    for j from 1 to i − 1
      if (A[j] > A[j + 1])
        swap the values of A[j] and A[j + 1]

上面两个算法有着明显的差别。第一个算法外层循环一次,会有一个最小的元素从底部冒泡到顶部。 而第二个算法,外层循环一次,会有一个最大的元素下沉到底部。那么到底哪个才是冒泡排序呢?

Bubble Sort: An Archaeological Algorithmic Analysis 对冒泡排序的来历做了很详细的分析。但有趣的是,这一算法似乎找不到一个明确的发明人。 比较早的一个出处是Kenneth Iverson的 A Programming Language, 1962.

这本书中的一个例子很好的说明了这个泡到底应该怎么冒。

Bubble sort example

Introduction to Algorithms 与上图中的例子是一致的。而 The Algorithm Design Manual 中的算法,虽然也有好多书中将其称为冒泡排序,但也有一些书中将其称为push down sort或者jump down sort。

我个人更倾向于 Introduction to Algorithms 中的实现。 下面是我用C++实现的冒泡排序算法。

template <typename T>
void bubble_sort(T a[], int length)
{
  for (int i = 0; i < length - 1; ++)
    for (int j = length - 1; j > i; --j)
      if (a[j] < a[j - 1])
        std::swap(a[j], a[j - 1]);
}

冒泡排序算法在最坏情况下的时间复杂度是\( O(n^2) \),空间复杂度是\( O(1) \)。