冒泡排序是一種極其簡單的排序算法，也是我所學(xué)的第一個(gè)排序算法。它重復(fù)地走訪過要排序的元素，一次比較相鄰兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們調(diào)換過來，直到?jīng)]有元素再需要交換，排序完成。這個(gè)算法的名字由來是因?yàn)樵叫?或越大)的元素會(huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

冒泡排序算法的運(yùn)作如下：

比較相鄰的元素，如果前一個(gè)比后一個(gè)大，就把它們兩個(gè)調(diào)換位置。

對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會(huì)是最大的數(shù)。

針對所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

分類--------------內(nèi)部比較排序

數(shù)據(jù)結(jié)構(gòu)----------數(shù)組

最差時(shí)間復(fù)雜度---- O(n^2)

最優(yōu)時(shí)間復(fù)雜度----如果能在內(nèi)部循環(huán)第一次運(yùn)行時(shí),使用一個(gè)旗標(biāo)來表示有無需要交換的可能,可以把最優(yōu)時(shí)間復(fù)雜度降低到O(n)

平均時(shí)間復(fù)雜度---- O(n^2)

所需輔助空間------ O(1)

穩(wěn)定性------------穩(wěn)定

#include

usingnamespacestd;

voidexchange(intA[],inti,intj)//交換A[i]和A[j]

{

inttemp = A[i];

A[i] = A[j];

A[j] = temp;

}

intmain()

{

intA[] = {6,5,3,1,8,7,2,4};//從小到大冒泡排序

intn =sizeof(A) /sizeof(int);

for(intj =0; j < n -1; j++)//每次最大元素就像氣泡一樣"浮"到數(shù)組的最后

{

for(inti =0; i < n -1- j; i++)//依次比較相鄰的兩個(gè)元素,使較大的那個(gè)向后移

{

if(A[i] > A[i +1])//如果條件改成A[i] >= A[i + 1],則變?yōu)椴环€(wěn)定的排序算法

{

exchange(A, i, i +1);

}

}

}

printf("冒泡排序結(jié)果：");

for(inti =0; i < n; i++)

{

printf("%d ", A[i]);

}

printf("\n");

return0;

}