冒泡排序

/*
 * bubbleSort.cpp
 * 冒泡排序，算法导论 P23
 *  Created on: 2011-12-28
 *      Author: LiChanghai
 */

template<typename T>
void bubbleSort(T array[ ], int n)
{
    //定义哨兵，当其中一趟没有元素交换顺序的时候
    //说明数组已经有序，排序结束
    bool flag=1;

    int i, j =0;
    T temp;
    for(i=0; i<n; ++i)
    {
        flag = 0; //每一趟开始前对flag清0
        for(j=n-1; j>i; --j)
            if(array[j]<array[j-1])
            {
                temp = array[j-1];
                array[j-1] = array[j];
                array[j] = temp;
                flag = 1; //有数据交换顺序，flag置1
            }
        if(flag==0) //数组已经有序
            break;
    }

}