冒泡排序

水底的气泡是逐渐上浮的，而不是一下子就到达水面。冒泡排序与之类似，当用冒泡排序算法对一个无序序列升序排序时，后面较小的元素与前面较大的元素逐个交换位置，直到无元素交换为止，则整个序列成为一个有序序列。

冒泡排序的时间复杂度为O(n2)，空间复杂度为O(1)，当原始序列已经有序，则冒泡排序的时间复杂度为O(n)。当待排序序列基本有序时，使用冒泡排序速度往往比较快。

以一个整数序列的为例，冒泡排序过程见下表。

90 29 11 51 38 38 27 95 18 24 52 35 77 93 40 75

待排序序列

11 90 29 18 51 38 38 27 95 24 35 52 40 77 93 75

1趟后的结果

11 18 90 29 24 51 38 38 27 95 35 40 52 75 77 93

2趟后的结果

11 18 24 90 29 27 51 38 38 35 95 40 52 75 77 93

3 趟后的结果

11 18 24 27 90 29 35 51 38 38 40 95 52 75 77 93

4趟后的结果

11 18 24 27 29 90 35 38 51 38 40 52 95 75 77 93

5趟后的结果

11 18 24 27 29 35 90 38 38 51 40 52 75 95 77 93

6趟后的结果

11 18 24 27 29 35 38 90 38 40 51 52 75 77 95 93

7趟后的结果

11 18 24 27 29 35 38 38 90 40 51 52 75 77 93 95

8趟后的结果

11 18 24 27 29 35 38 38 40 90 51 52 75 77 93 95

9趟后的结果

11 18 24 27 29 35 38 38 40 51 90 52 75 77 93 95

10趟后的结果

11 18 24 27 29 35 38 38 40 51 52 90 75 77 93 95

11趟后的结果

11 18 24 27 29 35 38  38 40 51 52 75 90 77 93 95

12趟后的结果

11 18 24 27 29 35 38 38 40 51 52 75 77 90 93 95

13趟后的结果

11 18 24 27 29 35 38 38 40 51 52 75 77 90 93 95

排序完毕

 1 template <typename RandomIterator, typename Compare>
 2 void bubble_sort(RandomIterator first, RandomIterator last, Compare cmp)
 3 {
 4   if(first == last || first + 1 == last) return;
 5   for(bool exchanged = true; exchanged && first != last; ++first)
 6   {
 7     exchanged = false;
 8     for(RandomIterator current = last - 1; current != first; --current)
 9     {
10       RandomIterator prev = current - 1;
11       if(cmp(*current, *prev))
12       {
13          swap(*current, *prev); // 本主页介绍的快排里有swap实现，用于交换两个元素
14          exchanged = true;
15       }
16     }
17   }
18 }