python实现冒泡排序

ゝ一纸荒年。 2024-03-30 10:30 50阅读 0赞

[  
python算法][python] \- python实现冒泡排序

[冒泡排序][Link 1]的运算原理：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

实例代码

## \-*- 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): 一个序列对象。
    
       cmp (Function): 比较函数。默认为内建函数cmp()。

*  1
 *  2
 *  3

Returns:

一个排序后的列表。

*  1

“”"

if (seq == None):

return None

*  1

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]

*  1
 *  2
 *  3
 *  4
 *  5

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)

*  1
 *  2
 *  3
 *  4
 *  5

def test\_bubble\_sort():

print(items)
    
       sorted_items = bubble_sort(items)
    
       print(sorted_items)

*  1
 *  2
 *  3
 *  4
 *  5

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))

来源：[https://www.weidianyuedu.com][https_www.weidianyuedu.com]

[python]: https://so.csdn.net/so/search?q=python%E7%AE%97%E6%B3%95&spm=1001.2101.3001.7020
[Link 1]: https://so.csdn.net/so/search?q=%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F&spm=1001.2101.3001.7020
[timeit]: https://so.csdn.net/so/search?q=timeit&spm=1001.2101.3001.7020
[https_www.weidianyuedu.com]: https://www.weidianyuedu.com