冒泡排序及其时间、空间复杂度解析

1.冒泡排序

1.概念及思路：重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故称为"冒泡排序"。
2.代码实现：

#include<iostream>
using namespace std;
void BubbleSort(int *a, int size)
{
 for (int i = 0; i < size; i++)//外循环，循环每个元素
 {
  for (int j = 1; j < size - i; j++)//内循环进行元素的两两比较
  {
   if (a[j] < a[j - 1])//判断相邻元素并进行交换
   {
    int temp = a[j];
    a[j] = a[j - 1];
    a[j - 1] = temp;
   }
  }
 }
}
int main()
{
 int a[10] = { 2, 7, 34, 54, 12, 5, 19, 33, 88, 23 };
 cout << "原来的数组为:" << endl;
 for (int i = 0; i < 10; i++)
 {
  cout << a[i] << " ";
 }
 cout << endl;
 BubbleSort(a, 10);
 cout << "冒泡排序后的数组为：" << endl;
 for (int i = 0; i < 10; i++)
 {
  cout << a[i] << " ";
 }
 return 0;
}

运行结果为:

时间复杂度:外循环和内循环以及判断和交换元素的时间开销。
最优的情况也就是开始就已经排序好序了，那么就可以不用交换元素了，由于外层循环为n,内层所需要循环比较的次数为（n-1）、（n-2）…1由等差数列求和得时间花销为：[ n(n-1) ] / 2；所以最优的情况时间复杂度为：O( n^2 )。
最差的情况也就是开始的时候元素是逆序的，那么每一次排序都要交换两个元素，则时间花销为：[ 3n(n-1) ] / 2；（其中比上面最优的情况所花的时间就是在于交换元素的三个步骤）；所以最差的情况下时间复杂度为：O( n^2 )；
空间复杂度：冒泡排序的辅助变量空间仅仅是一个临时变量，并且不会随着排序规模的扩大而进行改变，所以空间复杂度为O(1)。