冒泡排序算法实例详解-数据结构与算法教程

1.复杂度与稳定性

算法时间复杂度

最坏情况：O(n^2)

最好情况：O(n)

平均情况：O(n^2)

空间复杂度：S(n)=O(1)

稳定性：稳定排序

2.过程介绍（以顺序为例）

1.从第一个元素开始逐个比较相邻的元素。如果第一个比第二个大（a[1]>a[2]），就交换他们两个。

2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。此时在这一点，最后的元素应该会是最大的数，我们也称呼一遍这样的操作为：一趟冒泡排序。

3.针对所有的元素重复以上的步骤，每一趟冒泡排序的最大值已放在最后，下一次操作则不需要将此最大值纳入计算计算。

4.持续对每次对越来越少的元素，重复上面的步骤，直到没有任何一对数字需要比较，即完成冒泡排序。

3.图示过程

以数组数据{ 70,50,30,20,10,70,40,60}为例：

如此图，每一次排序结尾，总有一个最大的数被放在了最后，然后这个趋势逐渐往前，但是，到了第四趟的时候，其实我们整个数据已经排序结束了，但是此时我们的程序还在进行，直到第5，6，7趟结束程序才算真正的结束，这其实是一种浪费算力的表现。

4.相关的代码

#include<iostream>
using namespace std;
void bubble_sort(int a[],int n) {
    for(int i=0; i<n; i++) {
        for(int j=0; j<n-i; j++) {
            if(a[j]>a[j+1]) {
                swap(a[j],a[j+1]);  //交换数据
            }
        }
    }
}
 
int main() {
    int a[8]= {70,50,30,20,10,70,40,60};
    int n=7;
    bubble_sort(a,n);
    for(int i=0; i<=n; i++) {
        cout<<a[i]<<' ';
    }
    return 0;
}

在这里提示一下，由于C++的namespace std命名空间的使用，std自带了交换函数swap(a,b)，我们可以直接使用，其功能是交换a与b的两个值，在教程后面的排序中会经常用到，当然你可以自定义swap函数，其模板代码为：

template<class T>        //模板类，可以让参数为任意类型
void swap(T &a,T &b) {
    T c(a);
    a=b;
    b=c;
}

或者指定类型修改为整形，如：

void swap(int &a, int &b) { //指定类型
    int temp = a;
    a = b;
    b = temp;
}

那么我们的冒泡排序就算学完了，其实冒泡排序是八大排序中最简单及基础的排序，这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。