python算法 - python实现冒泡排序
冒泡排序的运算原理：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
立即学习“Python免费学习笔记（深入）
”；
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
实例代码# -*- 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]4 then exchange A[j] ↔ A[j-1]T(n) = θ(n^2) Args:seq (Sequence): 一个序列对象。
cmp (Function): 比较函数。默认为内建函数cmp()。
Returns:一个排序后的列表。
"""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], 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))