您好,登錄后才能下訂單哦!
【六月五號(hào)】排序算法之冒泡排序
今天說(shuō)的仍然是一中簡(jiǎn)單排序——冒泡排序,時(shí)間復(fù)雜度O(n^2)。
其基本思想是:
通過(guò)相鄰元素之間的比較和交換使較小的元素逐漸從后向前移動(dòng),就像水底的氣泡一樣逐漸向上冒。
具體過(guò)程如下:
首先比較d[n]和d[n-1],若d[n]<d[n-1],則交換,使較小的元素前移,較大的元素后移;接著比較d[n-1]和d[n-2],以此類(lèi)推,直到比較d[2]和d[1]并使較小的元素前移,第一趟排序結(jié)束,則d[1]為最小的元素。然后在d[2]..d[n]間進(jìn)行第二趟排序,使第二小元素前移到d[2]位置;n-1趟排序后,整個(gè)冒泡排序結(jié)束。
假設(shè)我們將把225 220 41 190 242 185 42 231這8個(gè)數(shù)排序
排序過(guò)程演示
初始關(guān)鍵字:[225 220 41 190 242 185 42 231]不交換
d[8]和d[7]:[225 220 41 190 242 185 42 231]交換
d[7]和d[6]:[225 220 41 190 242 42 185 231]交換
d[6]和d[5]:[225 220 41 190 42 242 185 231]交換
d[5]和d[4]:[225 220 41 42 190 242 185 231]不交換
d[4]和d[3]:[225 220 41 42 190 242 185 231]交換
d[3]和d[2]:[225 41 220 42 190 242 185 231]交換
d[2]和d[1]:[41 225 220 42 190 242 185 231]
以上是一趟排序的演示,總共需要進(jìn)行n-1趟排序
第一趟排序后:41 [225 220 42 190 242 185 231]
第二趟排序后:41 42 [225 220 185 190 242 231]
第三趟排序后:41 42 185 [225 220 190 231 242]
第四趟排序后:41 42 185 190 [225 220 231 242]
第五趟排序后:41 42 185 190 220 [225 231 242]
第六趟排序后:41 42 185 190 220 225 [231 242]
第七趟排序后:41 42 185 190 220 225 231 242
Pascal代碼:
const mx=10000;
var
d:array[1..mx]of longint;
n,i,j,k:longint;
begin
readln(n);
for i:=1 to n do read(d[i]);
for i:=1 to n-1 do
begin
for j:=n-1 downto i do
if d[j+1]<d[j] then
begin //相鄰元素交換
k:=d[j]; d[j]:=d[j+1]; d[j+1]:=k;
end;
end;
for i:=1 to n do writeln(d[i]);
End.
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。