冒泡排序

引论

这里来介绍一个应该算是最简单的排序算法—冒泡排序。冒泡排序的思想就是一次比较两个元素，如果元素的顺序错误，就交换着两个元素的位置，重复这一步骤直到没有错误的顺序为止。因为冒泡排序会使值比较小的元素从底部一步步的向上，知道顶部，就像小气泡从水中向上冒一样，因此取名冒泡排序。

算法流程

• 比较相邻的两个元素，如果第一个大于第二个，就交换两个元素，否则不做任何事情。

• 依次对每一对元素做相同操作（如第二个元素与第三个元素），直到最后一个元素。

• 对除了最后一个元素外的所有元素重复上面的步骤。

• 重复上面的步骤，直到排序完毕。

冒泡排序的算法复杂度为O（N^2）。冒泡排序是一个思想很简单，但是执行起来很糟糕的算法，因为他要比较（N-1）*N/2次，而且它很难利用之前操作的一些有序的信息。

代码实现

void BubbleSort(ElementType A[], int N)  
{  
    int i,j,tmp;  
    for(i=0;i<N;i++)  
        for(j=N-1;j>i;j--)  
        {  
            if(A[j]<A[j-1])  
            {  
                tmp = A[j-1];  
                A[j-1] = A[j];  
                A[j] = tmp;  
            }  
        }  
}

从时间复杂度上看，冒泡排序是个机器糟糕的算法