冒泡排序

水底的氣泡是逐漸上浮的，而不是一下子就到達水面。冒泡排序與之類似，當用冒泡排序算法對一個無序序列升序排序時，后面較小的元素與前面較大的元素逐個交換位置，直到無元素交換為止，則整個序列成為一個有序序列。

冒泡排序的時間復雜度為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 }