python算法 - python實(shí)現(xiàn)冒泡排序

冒泡排序的運(yùn)算原理：

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

對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。

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

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

實(shí)例代碼

# -*- encoding: utf-8 -*-


def bubble_sort(seq, cmp=cmp):

   """冒泡排序，偽碼如下：

   BUBBLESORT(A)

   1  for i ← 1 to length[A]

   2    do for j ← length[A] downto i+1

   3      do if A[j] < A[j-1]

   4        then exchange A[j] ? A[j-1]


   T(n) = θ(n^2)


   Args:

       seq (Sequence): 一個(gè)序列對(duì)象。

       cmp (Function): 比較函數(shù)。默認(rèn)為內(nèi)建函數(shù)cmp()。


   Returns:

       一個(gè)排序后的列表。

   """

   if (seq == None):

       return None

   length = len(seq)


   for i in range(length):

       for j in range(length-1, i, -1):

           if seq[j] < seq[j-1]:

               seq[j], seq[j-1] = seq[j-1], seq[j]


   return seq


if __name__ == '__main__':

   import random, timeit


   items = range(10000)

   random.shuffle(items)


   def test_sorted():

       print(items)

       sorted_items = sorted(items)

       print(sorted_items)


   def test_bubble_sort():

       print(items)

       sorted_items = bubble_sort(items)

       print(sorted_items)


   test_methods = [test_sorted, test_bubble_sort]

   for test in test_methods:

       name = test.__name__ # test.func_name

       t = timeit.Timer(name + '()', 'from __main__ import ' + name)

       print(name + ' takes time : %f' % t.timeit(1))

標(biāo)簽： 代碼

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。