冒泡排序

参考：http://www.cnblogs.com/skywang12345/p/3596232.html

//冒泡排序
#include<iostream>

using namespace std;

void BubbleSort(int* a, int nLen)
{
    if (a == nullptr || nLen <= 0)
        return;
    //每次冒泡都能把最大的放在最后
    for (int i = nLen - 1; i >= 0; i--)
    {
        for (int j = 0; j < i; j++)
        {
            if (a[j] > a[j + 1])
            {
                int nTmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = nTmp;
            }
        }
    }
}


int main()
{
    int a[10] = {10,9,8,6,5,3,2,1,4,7};
    int nLen = sizeof(a) / sizeof(a[0]);
    cout << nLen<<endl;
    for (int i = 0; i < nLen; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
    BubbleSort(a,nLen);

    for (int i = 0; i < nLen; i++)
    {
        cout << a[i] << " ";
    }
    system("pause");
}

假设排序的序列中有N个数，遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？N-1次。
因此冒泡排序的时间复杂度是O(N^2)。