排序算法——冒泡排序

一、算法介绍

1.算法思想

冒泡排序的基本思想就是通过两两比较相邻元素，将较大（或较小）的元素往后交换，这样每经过一趟交换，就可将当前序列中最大的元素交换到最后的位置，并且该元素不参与下一趟交换，这样经过n-1趟交换后，即可完成对序列的升序（或降序）排序。

2.优化思路

若序列本身是基本有序的状态，那么可能经过几趟交换后，序列就已经提前达到有序状态，但是次数算法并不会退出，它会固定的执行n-1趟，但是不会再发生元素位置交换，那么此时我们可以设置一个标志位，用来标记每趟冒泡内部是否发生元素交换，若没有发生，则说明序列已经提前达到有序状态，此时直接返回退出，从而一定程度上提高算法的效率。

3.算法流程

图片来源于网络

每趟排序对相邻两个元素进行比较，将较大的元素往后交换，相同或小于则不会交换。每完成一趟排序，待排序序列长度减一，即上一趟排序交换到最后面的元素不参与下一趟排序。

二、算法实现

1.代码实现

#include<iostream>
using namespace std;
void BubbleSort(int* arr, int size) {
  for (int i = 0; i < size - 1; i++) {
  int flag = 1;//标记是否发生交换
  for (int j = 0; j < size - i - 1; j++) {//两两比较
    if (arr[j] > arr[j + 1]) {
    swap(arr[j], arr[j + 1]);//交换元素位置
    flag = 0;
    }
  }
  if (flag) {//提前达到有序
    return;
  }
  }
}
void PrintArr(int* arr, int size) {//数组打印
  for (int i = 0; i < size; i++) {
  cout << arr[i] << ' ';
  }
}
void Test() {
  int arr[] = { 2,5,4,8,7,1,3,9,6 };
  int size = sizeof(arr) / sizeof(arr[0]);
  cout << "排序前：";
  PrintArr(arr, size);
  BubbleSort(arr, size);
  cout << endl << "排序后：";
  PrintArr(arr, size);
  cout << endl;
}
int main() {
  Test();
  return 0;
}

2.测试用例及结果

测试用例：

arr[]={2,5,4,8,7,1,3,9,6}

测试结果：

三、性能分析

1.时间复杂度

最坏情况

根据算法排序思想可知，最坏情况即序列初始状态为逆序时，此时算法需要执行n-1趟，且每趟的相邻量元素都需要交换，所以最坏情况下的时间复杂度为 。

最好情况

同样，最好情况即序列初始已经是有序状态，每趟都不需要发生交换，根据优化思路，只需要遍历一遍序列，发现没有发生元素交换，算法就会立刻退出返回，所以最好情况下的时间复杂度为O(n)。

平均情况

综合两种情况，冒泡排序的时间复杂度为 。

2.空间复杂度

由于算法实现中只使用了几个临时变量作为标记，没有借助额外的辅助空间，所以空间复杂度为O(1)。

3.稳定性

因为排序思想是对序列进行顺序遍历并两两比较，将较大的元素往后交换，相同时不会发生交换，所以不会改变相同元素的相对位置，所以冒泡排序是稳定的。