冒泡排序（Bubble Sort）

  • 平均时间复杂度：O(n)
  • 最好情况：O(n) ——遍历一次发现没有任何可以交换的元素，排序结束
  • 最坏情况：O(n)——反序列情况下最坏
  • 空间复杂度：O(1)
  • 排序方式：内部
  • 稳定性：稳定

    C++代码实现

    1. void bubbleSort(vector<int>& arr) {
    2.   int len = arr.size();
    3.   //(优化②)记录最后一次交换的位置
    4.   int lastExchangeIndex = 0;
    5.   int sortBorder = len-1;
    6.   for(int i = 0; i < len; i++) {
    7.       //(优化①)有序标记，每一轮的初始是true
    8.       bool isSorted = true;
    9.       for(int j = 0 ; j < sortBorder; j++) {
    10.           if(arr[j] > arr[j+1]){                //cmp
    11.               swap(arr[i],arr[j]); 
    12.               //(优化①)有元素交换，所以不是有序，标记变为false
    13.               isSorted = false;
    14.               //(优化②)把无序数列的边界更新为最后一次交换元素的位置
    15.               lastExchangeIndex = j;
    16.           }    
    17.       }
    18.       //(优化①) 没有交换操作，排序结束
    19.       if(isSorted) break;
    20.       //(优化②)从0~最后一次交换位置排序
    21.       sortBorder = lastExchangeIndex;
    22.   }
    23. }

1. 算法步骤

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个；
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数；
  3. 针对所有的元素重复以上的步骤，除了最后一个；
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较；

    优化步骤

    ① 如果某次内循环中没有交换操作，说明序列已经有序，结束排序；
    ② 当序列后部分有序时，只需记下最后交换的下标位置，后面已经有序；
    ③ 鸡尾酒算法优化（本篇未实现）20170312144555263.gif

2. 动图演示（无优化）

冒泡排序 - 图2