冒泡排序算法原理

冒泡法是一種簡單的排序方法，它的實現非常簡單。首先對n個項目進行掃描，比較相領兩個項目的大小，若發(fā)現違背大小次序則進行互換，由此可以使n個項目中的最大者換到最后。

然后對剩下的未排序好的項目再進行掃描，使它們的最大者換到表的最后。以此類推，直到將表全部排序好為止。這種排序方法，每遍掃描以后，都縮短了待排序表的長度，如果在某次掃描過程中，沒有發(fā)現交換，則排序結束。

冒泡排序算法原理

1、從后往前依次比較相鄰的元素。若是要按照升序排序，則后面的元素比前面的小，就交換這2個元素；降序則相反。

2、對每一對相鄰元素作同樣的工作，從第一對到最后一對。進行一輪比較交換下來，最后的元素就會是最?。ɑ蜃畲螅┑臄盗?，這個數就不用參與后面的比較操作了。

3、針對所有的元素重復以上的步驟。

4、持續(xù)每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

為了盡量縮短待排序表的長度，避免下一次掃描中可能出現的不必要的比較，在每次掃描過程中，一方面要記錄進行元素交換的次數，另一方面要記住在本次掃描中的最后一次進行交換的位置。在這個位置以后沒有發(fā)生過交換，則說明在這個位置以后的元素實際上已經排好次序。

總的來說，冒泡法基本思想是重復的進行整個數組的排序，一次比較兩個元素(兩兩排序)，如果它們順序不符合就交換，重復這樣直到數列沒有再需要交換的數為止(結束條件)。因為它就好像氣泡一樣，輕的氣泡會往上漂浮，在不斷漂浮的過程中，發(fā)生了兩兩交換過程，所以叫冒泡排序。

實例說明：

輸入：待排序表L（1:n）。

輸出：有序表L（1:n）。

PROCEDURELBUBSORT(L,N)

F←n

WHILEF>0DO

{k←F-1:F←0

FORj=1TOkDO

{IFL(j)>L(j+1)THEN

{L(j)與L(j+1)交換:F←j}

}

}

RETURN

在這個算法中，k代表在每次掃描過程中需要進行經較的項目數；當F＞0時，表示還需要進行掃描比較，并且，它的數值表示上一次掃描中發(fā)生最后一次交換的位置。由上例可知，在最壞情況下，冒泡排序法需要進行n-1遍掃描，共要作[n(n-1)]/2次比較和元素的交換。但這個工作量并不是必需的，一般情況下要小于這個工作量。