冒泡排序(BubbleSort)

应该是最基础的一个排序方法啦，大一老师就讲过的，所以在我脑海中也是最熟的一个排序算法了.

冒泡排序顾名思义，在每躺冒泡中，大的关键字像石头一样“沉底”，小的关键字像气泡一样逐渐向上“浮动”，最终使得整个序列有序（这个概念解释好苍白hhhhh）

代码：

#include <iostream>
using namespace std;

void BubbleSort(int array[], int n) {
  int i, j, temp, flag;

  for (i = 0; i < n; ++i) {
    flag = 0;
    for (j = i; j < n-1; ++j) {
      if (array[j] > array[j+1]) {
        temp = array[j];
        array[j] = array[j+1];
        array[j+1] = temp;
        flag = 1;
      }
    }
    if (flag == 0){
      /* 一趟排序过程中没有发生关键字交换
       * 则证明序列有序，排序结束*/
      return;
    }
  }
}

void print_array(int array[], int n){
  for (int i = 0; i < n; ++i)
    cout<<array[i]<<" ";
  cout<<endl;
}

int main() {
  int array[] = {1, 3, 8, 4, 6, 7};
  print_array(array, 6);
  BubbleSort(array, 6);
  print_array(array, 6);

  return 0;
}

复杂度分析：

1. 时间复杂度：
1）最坏情况：内层循环每次都执行， 故时间复杂度为O(n^2)
2）最好情况：原本就有序，内层循环不发生，时间复杂度为O(n)
综合来看，时间复杂度为O(n^2).

2. 空间复杂度：
只需要一个temp， 故空间复杂度为O(1)。