排序——冒泡排序

冒泡排序也成为气泡排序。冒泡排序法的思想是：从头到尾比较相邻的两个元素，将小的换到前面，大的换到后面。经过了从头到尾的一趟比较，就把最大的元素交换到了最后一个位置。这个过程称为一趟起泡。然后再从头开始到倒数第二个元素进行第二趟起泡。经过了第二趟比较，又将第二大的元素放到了倒数第二个位置……依此类推，经过第n-1趟起泡，将倒数第n-1个大的元素放人第二个单元。此时，最小的元素就放在了第一个单元，完成排序。

#include <iostream>
#include <vector>
using namespace std;


template<class T>
void bubbleSort(vector<T> &a)
{
    for(int i = 1; i < a.size(); ++i){
        bool flag = false;

        for(int j = 0; j < a.size() - i; ++j){
            if(a[j] > a[j + 1]){
                swap(a[j], a[j + 1]);
                flag = true;
            }
        }
        if(!flag) break;
    }
}


int main()
{
    vector<int> a = {9,8,7,6,5,4,3,2,1};

    bubbleSort(a);

    for(int i = 0; i < a.size(); ++i)
        cout << a[i] << '\t' ;

    return 0;
}

典型应用：

• 一本通-1310：【例2.2】车厢重组（冒泡排序）