冒泡算法

冒泡排序的基本思想是：每次比較兩個(gè)相鄰的元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)

1、從第一個(gè)數(shù)據(jù)開始，與第二個(gè)數(shù)據(jù)相比較，如果第二個(gè)數(shù)據(jù)小于第一個(gè)數(shù)據(jù)，則交換兩個(gè)數(shù)據(jù)的位置。
2、指針由第一個(gè)數(shù)據(jù)移向第二個(gè)數(shù)據(jù)，第二個(gè)數(shù)據(jù)與第三個(gè)數(shù)據(jù)相比較，如果第三個(gè)數(shù)據(jù)小于第二個(gè)數(shù)據(jù)，則交換兩個(gè)數(shù)據(jù)的位置。
3、依此類推，完成第一輪排序。第一輪排序結(jié)束后，最大的元素被移到了最右面。
4、依照上面的過(guò)程進(jìn)行第二輪排序，將第二大的排在倒數(shù)第二的位置。
5、重復(fù)上述過(guò)程，沒排完一輪，比較次數(shù)就減少一次。

代碼：

#include <stdio.h>

int main()
{
   int a[10],i,j,t,n = 10; 
    for(i = 1; i <= n; i++)
    {
        a[i] = i - 1;
    }
    //核心部分
    for(i = 1; i <= n; i++)
        for(j = 1;j <= n - i; j++)
        {
            if(a[j] <= a[j + 1])
            {
                t = a[j];a[j] = a[j + 1];a[j + 1] = t;
            }
        }
   for(i = 1; i <= n; i++)
       printf("%d ",a[i]);
    getchar();
   return 0;
}

運(yùn)行結(jié)果：

9 8 7 6 5 4 3 2 1 0 

時(shí)間復(fù)雜度：

O(N2)

總結(jié)：如果有n個(gè)數(shù)進(jìn)行排序，只需將n-1個(gè)數(shù)歸位，也就是說(shuō)要進(jìn)行n-1趟操作，而“每一趟”都需要從第1位開始進(jìn)行相鄰兩個(gè)數(shù)的比較，將較小的一個(gè)數(shù)放在后面，比較完畢向后挪一位繼續(xù)比較下面兩個(gè)相鄰數(shù)的大小，重復(fù)此步驟，直到最后一個(gè)尚未歸位的數(shù)，已經(jīng)歸位的數(shù)無(wú)需在比較