數(shù)據(jù)結(jié)構(gòu)0405冒泡排序

冒泡排序交換排序的基本思想兩兩比較待排序記錄的關(guān)鍵字，一旦發(fā)現(xiàn)兩個(gè)記錄不滿足次序要求時(shí)則進(jìn)行交換，直到整個(gè)序列全部滿足要求為止。冒泡排序冒泡排序就是一種最簡(jiǎn)單的交換排序方法，它通過兩兩比較相鄰記錄的關(guān)鍵字，如果發(fā)生逆序，則進(jìn)行交換，從而使關(guān)鍵字小的記錄如氣泡般逐漸往上“漂浮”，對(duì)應(yīng)順序表就是往左移動(dòng)，或者使關(guān)鍵字大的記錄如石塊一樣逐漸“下沉”，對(duì)應(yīng)順序表的右移。也正是這個(gè)原因，我們稱這種排序方法為冒泡排序。例題設(shè)待排序記錄為：4938659776132730

012345678910493865977613273049>38第一輪排序例題設(shè)待排序記錄為：4938659776132730

0123456789103865977613273049>3849第一輪排序例題設(shè)待排序記錄為：4938659776132730

012345678910384965977613273049<65第一輪排序例題設(shè)待排序記錄為：4938659776132730

012345678910384965977613273065<97第一輪排序例題設(shè)待排序記錄為：4938659776132730

012345678910384965977613273097>76第一輪排序例題設(shè)待排序記錄為：4938659776132730

012345678910384965977613273097>76第一輪排序例題設(shè)待排序記錄為：4938659776132730

012345678910384965769713273097>13第一輪排序例題設(shè)待排序記錄為：4938659776132730

012345678910384965769713273097>13第一輪排序例題設(shè)待排序記錄為：4938659776132730

012345678910384965761397273097>27第一輪排序例題設(shè)待排序記錄為：4938659776132730

012345678910384965761397273097>27第一輪排序例題設(shè)待排序記錄為：4938659776132730

012345678910384965761327973097>30第一輪排序例題設(shè)待排序記錄為：4938659776132730

012345678910384965761327973097>30第一輪排序例題設(shè)待排序記錄為：4938659776132730

0123456789103849657613273097第一輪排序結(jié)果冒泡排序的算法voidbubble_sort(SqList&L){intm,i,j,flag=1;RedTypex;m=L.length-1;while((m>0)&&(flag==1)){flag=0;for(j=1;j<=m;j++)if(L.r[j].key>L.r[j+1].key){flag=1;x=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=x;//交換

}//endifm--;}//endwhile}冒泡排序的算法效率最壞情況下，總的關(guān)鍵字比較次數(shù)KCN為KCN==n(n-1)/2≈n2/2記錄移動(dòng)次數(shù)RMN為RMCN==3n(n-1)/2≈3n2/2RMN之所以要乘以3，是因?yàn)槊看谓粨Q都要移動(dòng)3次記錄。所以，冒泡排序的時(shí)間復(fù)雜度為O(n2)

時(shí)間復(fù)雜度方面，最好情況下，待排序記錄已經(jīng)有序，則只需進(jìn)行一趟排序，在排序過程中進(jìn)行n-1次關(guān)鍵詞比較，并且不移動(dòng)記錄。冒泡排序的算法效率

空間復(fù)雜度方面，冒泡排序只