一天一算法之冒泡排序

时间复杂度O（n^2）

基本思想：

    对待排序的序列进行依次比较相邻的两个对象，并且把大的对象放在后面，小的对象放在前面。每一轮排序结果都会使待排序的序列中最大值有序；算法直到序列有序后结束。整个排序的过程可以使用二次循环实现。 

实现代码：

template < class T >
 void  BubbleSort(T * aList, size_t size)
 {
     unsigned int i, j;
     T temp;
     for (i = 0 ; i < size; ++ i)
    {
        for (j = 0 ; j < size - i - 1 ; ++ j)
        {
            if (aList[j] > aList[j + 1 ])
            {
                temp = aList[j + 1 ];
                aList[j + 1 ] = aList[j];
                aList[j] = temp;
            }
        }
    }
}

  

此算法是最基本的冒泡排序，未加任何优化

以下版本添加了优化条件判断，效率会高一点

  

template < class T >
void  BubbleSort(T * aList, size_t size)
{
    unsigned int i, j;
    T temp; bool  isSorted;
    for (i = 0 ; i < size; ++ i)
    {
        isSorted = true ;
        for (j = 0 ; j < size - i - 1 ; ++ j)
         {
            if (aList[j] > aList[j + 1 ])
            {
                isSorted = false ;
                temp = aList[j + 1 ];
                aList[j + 1 ] = aList[j];
                aList[j] = temp;
            }
         }
        if (isSorted)
        {
             break ;
         }
     }

view source

print?