冒泡排序

冒泡排序（英語(yǔ)：Bubble Sort）是一種簡(jiǎn)單的排序算法。它重復(fù)地遍歷要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。遍歷數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

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

1、比較相鄰的元素。如果第一個(gè)比第二個(gè)大（升序），就交換他們兩個(gè)。

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

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

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

冒泡排序，一個(gè)經(jīng)典的排序算法，因在算法運(yùn)行中，極值會(huì)像水底的氣泡一樣逐漸冒出來(lái)，因此而得名。

冒泡排序的過(guò)程是比較兩個(gè)相鄰元素的大小，然后根據(jù)大小交換位置，這樣從列表左端開(kāi)始冒泡，最后最大值會(huì)依次從右端冒出。 

python實(shí)現(xiàn)冒泡排序：

def bubble_sort(nums):

 for i in range(len(nums) - 1):

  for j in range(len(nums) - i - 1):

   if nums[j] > nums[j + 1]:

    nums[j], nums[j + 1] = nums[j + 1], nums[j]

 return nums

python實(shí)現(xiàn)冒泡排序的核心思想是通過(guò)從列表一端迭代循環(huán)元素，再通過(guò)一個(gè)循環(huán)讓這個(gè)元素之后的元素相鄰兩個(gè)比較，從而依次將最大值移動(dòng)到最末端，如下圖示意。

本想放gif圖的，放不上有點(diǎn)問(wèn)題。

關(guān)于冒泡排序的時(shí)間復(fù)雜度，在上面python實(shí)現(xiàn)的代碼中時(shí)間復(fù)雜度是n的平方，當(dāng)然可以再考慮一下極端的情況：當(dāng)隊(duì)列已經(jīng)從小到大排好序或者從大到小排好序，從小到大排好順序時(shí)可以只掃描一遍就結(jié)束排序，此時(shí)時(shí)間復(fù)雜度為O(n)，如果是從大到小，那么就需要掃描n-1次，同時(shí)需要比較交換n-1次，時(shí)間復(fù)雜度為n的平方 。

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)腳本之家的支持。