返回顶部

收藏

Python冒泡排序

更多
# -*- coding: 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] &#8596; 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-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))
#该片段来自于http://outofmemory.cn

标签:python,算法

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. 蓝鲸 发表 2017-07-21 02:04:07 使用python实现排序算法(Selection Sort)
  2. 0X55AA 发表 2015-04-29 05:29:52 DHT爬虫站-芭蕉细雨
  3. rainy 发表 2015-09-02 15:52:26 网页正文及内容图片提取算法
  4. 数控小V 发表 2016-02-17 03:14:02 机器学习算法 Python&R 速查表
  5. 上官 江 发表 2012-12-02 11:18:18 RC4算法Python实现
  6. 博主 发表 2012-02-29 23:24:00 AStar算法的python实现
  7. Yusheng 发表 2016-06-29 20:16:49 哈夫曼编码 —— Lisp 与 Python 实现
  8. 小数点 发表 2017-04-27 00:48:25 普通程序员如何向人工智能靠拢?
  9. 蓝鲸 发表 2017-09-15 02:05:05 使用python实现排序算法(Bubble Sort)
  10. 姚 广远 发表 2015-06-19 00:23:25 用Python实现各种排序算法
  11. Yushneng 发表 2016-04-25 13:51:00 可视化图的基本算法
  12. 0X55AA 发表 2014-07-22 13:23:03 whitespace的python实现

发表评论