4. 冒泡排序¶

4.1. 冒泡排序¶

我们的下一个排序算法叫做冒泡排序。冒泡排序常被用来教计算机科学导论课上的初学者。这很遗憾，因为冒泡排序毫无可取之处。与其他常见的 \(\Theta(n^2)\) 排序算法相比，它相当慢。它也谈不上直观——没有人在整理桥牌手牌或一堆账单时，会像想到插入排序或选择排序那样，自然而然地想到冒泡排序。不过，冒泡排序可以看作选择排序的近亲。

与插入排序类似，冒泡排序由简单的双重 for 循环构成。内层 for 循环从左到右扫过记录数组，比较相邻的键。如果一条记录的键值大于其右邻记录的键，就交换这两条记录。一旦遇到键值最大的记录，这个过程会让它"冒泡"到数组的右端（冒泡排序因此得名）。第二趟重复这个过程。不过，由于我们已经知道键最大的记录在第一趟就到了数组右端，第二趟无需再比较最右边的两条记录。同样地，之后每一趟都比较相邻记录，只是比上一趟少看末尾的一条记录。下面是一种实现。

Java
Java (Generic)
C++

void bubblesort(int[] A) {
  for (int i=0; i<A.length-1; i++) // Insert i'th record
    for (int j=1; j<A.length-i; j++)
      if (A[j-1] > A[j])
        swap(A, j-1, j);
}

void bubblesort(T[] A) {
  for (int i=0; i<A.length-1; i++) // Insert i'th record
    for (int j=1; j<A.length-i; j++)
      if (A[j-1].compareTo(A[j]) > 0)
        swap(A, j-1, j);
}

void bubblesort(Comparable* A[], int n) {
  for (int i = 0; i < n-1; i++) // Insert i'th record
    for (int j = 0; j < n-i; j++) 
      if (*A[j] > *A[j+1]) 
        swap(A, j, j+1);
}