冒泡排序

 

思路

  • 确定第1位:从后向前两两比较,把较小的放在前,较大的放在后。结束后,最小的已经在第1位了。
  • 确定第2位:从后向前两两比较,把较小的放在前,较大的放在后。直到第2位。结束后,第2小的已经在第2位了。
  • ……
  • 确定第n-1位:……

平均时间复杂度:O(n2)

实现

void bubble_sort(const int* a, int length){
    bool flag;
    for(int i = 0; i < length-1; i++){
        flag =  false;
        for(int j = length-1; j > i; j--){
            if(a[j] < a[j-1]){
                swap(a[j], a[j-1]);
                flag = true;
            }
        }
        if(!flag) return;
    }
}

关键点注释

  • 2层遍历嵌套。
  • 外遍历从0到length - 1,即:“思路”中确定第1位~确定n - 1位。
  • 内遍历从length - 1到i,即“思路”中从后向前。
  • 遍历体为“两两比较,把较小的放在前,较大的放在后”。
  • flag用于记录一次遍历中是否进行了交换。如果没有进行交换,说明已经排好了,可以直接结束。