算法三：冒泡排序（O(n^2)）

 

1. 冒泡排序

复杂度：平均：O(n^2)

        最好：O（n） 最好的情况下只需要进行一次排序即可

稳定性：不稳定

程序：

template <class T>

void BubbleSort(T *A,int n)

{

      T temp;

      int i,j,last;

      i=n-1;

      while(i>0)

      {

             last=0;

             for(j=0;j<i;++j)

             {

                    if(A[j+1]<A[j])

                    {

                           temp=A[j+1];

                           A[j+1]=A[j];

                           A[j]=temp;

                           last=j;

                    }

             }

             i=last;

      }

}