//冒泡排序O(n^2)

template<typename T>
void bubbleSort(vector<T>& a)
{
    int n=a.size();
    for(int i=n-1;i>=0;i--)
        for(int j=0;j<i;j++)
            if(a[j+1]<a[j]) swap(a[j+1],a[j]);//冒泡，每次将最大值沉入水底
}

//选择排序O(n^2)，选择排序没有提前终止的机会
template<typename T>
void selectSort(vector<T>& a)
{
    int n=a.size();
    for(int i=0;i<n;i++)
    {
        int minIndex=i;//存放最小值索引
        for(int j=i+1;j<n;j++)
            if(a[j]<a[minIndex]) minIndex=j;//寻找[i,n)区间的最小值索引
        swap(a[i],a[minIndex]);
    }
}

//插入排序O(n^2)，插入排序可以提前终止，对于近乎有序的数据非常实用
template<typename T>
void insertSort(vector<T>& a)
{
    int n=a.size();
    for(int i=1;i<n;i++)
    {
        T e=a[i];
        int j;
        for(j=i;j>0&&a[j-1]>e;j--)
        {
            a[j]=a[j-1];//通过赋值来代替交换操作，可以优化代码。一个交换操作包含三次赋值操作，很花费时间
        }
        a[j]=e;

    }
}