冒泡排序
水底的氣泡是逐漸上浮的，而不是一下子就到達水面。冒泡排序與之類似，當(dāng)用冒泡排序算法對一個無序序列升序排序時，后面較小的元素與前面較大的元素逐個交換位置，直到無元素交換為止，則整個序列成為一個有序序列。
冒泡排序的時間復(fù)雜度為O(n2)，空間復(fù)雜度為O(1)，當(dāng)原始序列已經(jīng)有序，則冒泡排序的時間復(fù)雜度為O(n)。當(dāng)待排序序列基本有序時，使用冒泡排序速度往往比較快。
以一個整數(shù)序列的為例，冒泡排序過程見下表。
| 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趟后的結(jié)果 |
| 11 18 90 29 24 51 38 38 27 95 35 40 52 75 77 93 | 2趟后的結(jié)果 |
| 11 18 24 90 29 27 51 38 38 35 95 40 52 75 77 93 | 3 趟后的結(jié)果 |
| 11 18 24 27 90 29 35 51 38 38 40 95 52 75 77 93 | 4趟后的結(jié)果 |
| 11 18 24 27 29 90 35 38 51 38 40 52 95 75 77 93 | 5趟后的結(jié)果 |
| 11 18 24 27 29 35 90 38 38 51 40 52 75 95 77 93 | 6趟后的結(jié)果 |
| 11 18 24 27 29 35 38 90 38 40 51 52 75 77 95 93 | 7趟后的結(jié)果 |
| 11 18 24 27 29 35 38 38 90 40 51 52 75 77 93 95 | 8趟后的結(jié)果 |
| 11 18 24 27 29 35 38 38 40 90 51 52 75 77 93 95 | 9趟后的結(jié)果 |
| 11 18 24 27 29 35 38 38 40 51 90 52 75 77 93 95 | 10趟后的結(jié)果 |
| 11 18 24 27 29 35 38 38 40 51 52 90 75 77 93 95 | 11趟后的結(jié)果 |
| 11 18 24 27 29 35 38 38 40 51 52 75 90 77 93 95 | 12趟后的結(jié)果 |
| 11 18 24 27 29 35 38 38 40 51 52 75 77 90 93 95 | 13趟后的結(jié)果 |
| 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實現(xiàn)，用于交換兩個元素
14 exchanged = true;
15 }
16 }
17 }
18 }