专栏首页奔跑的键盘侠Python——关于排序算法(冒泡法)

Python——关于排序算法(冒泡法)

这是奔跑的键盘侠的第96篇文章

前一阵发的一篇《关于多线程的应用》,本来要去某站爬取几个T的资源,爬了几百G以后重感冒,就休息了一周。未料再次开动时,网站已然设置了反爬机制

可能是我的多线程开的太猛了吧

(峰值时大概50个线程,一分钟能下载1G)

这个周末本想安心写一下关于编程常见的一个排序算法,发现无法爬取自然不甘心,于是折腾了两天还是没搞定

收拾一下心情,讲一下关于排序算法吧,排序问题是编程入门里老生常谈的问题,虽说python也有内置的排序语法而且很好用(sort、sorted),但是讲到数据结构这块,排序的几个常见算法还是有必要学习一下。

冒泡排序法(Bubble Sort)

冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素已经排序完成。 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。 百度百科

冒泡排序算法的原理:

比如要排序n个数字,进行n轮循环比较并操作。每一轮,都是将未排序过的数字,进行两两比较,将较大的数不断往后置换;每一轮都会将本轮中的最大数置于未排序数字中的末位。

举个例子:

有列表[6,3,1,5,4,2]

用冒泡法操作:

第一轮:

6,3比较,6大则6,3互换:

3,6,1,5,4,2

6,1比较,6大则6,1互换:

3,1,6,5,4,2

…………

3,1,5,6,4,2

3,1,5,4,6,2

3,1,5,4,2,6

第一轮结束,最大数6置于末位了。

第二轮:

只需将前5位进行排序即可,

3,1,5,4,2

3,1比较,3大则3,1互换:

1,3,5,4,2

3,5比较,3小则不动,用下一位5进行比较,

5,4比较,5大则5,4互换:

1,3,4,5,2

1,3,4,2,5

第二轮结束,本组最大数5置于末位了。

第三轮:

只需将前4位进行排序即可,

1,3,4,2

1,3比较,1小则不动,下一位,

3,4比较,3小则不动,下一位,

4,2比较,4大则4,2互换:

1,3,2,4

第三轮结束,本组最大数4置于末位了。

第四轮:

只需将前3位进行排序即可,

1,3,2

1,3比较,1小则不动,下一位,

3,2比较,3大则3,2互换:

1,2,3

第四轮结束,本组最大数3置于末位了。

第五轮:

只需将前2位进行排序即可,

1,2

1,2比较,1小则不动

1,2

第五轮结束,本组最大数2置于末位了。

排序结束。

冒泡排序总的平均时间复杂度为

。假设列表中的元素是刚好逆序的:比如[6,5,4,3,2,1]那第一轮就要交换5次,第二轮4次……1次0次,总共次数就是1/2*6*(5+0)也就是1/2*N*(N-1),时间复杂度是n的平方。

coding

#!/usr/bin/env python3.6
# -*- coding: utf-8 -*-
# @Time    : 2019-03-24 18:39
# @Author  : Ed Frey
# @File    : bubble_sort.py
# @Software: PyCharm
from time import clock

def timer(f):
    def _f(*args):
        t0 = clock()
        f(*args)
        return clock() - t0
    return _f

def bubble_sort(num:list):
    lenth = len(num)
    while lenth:
        for i in range(lenth-1):
            if num[i]>num[i+1]:
                num[i],num[i+1] = num[i+1],num[i]
        lenth -= 1
        print(num)
    return num

if __name__ == '__main__':
    num = [6,3,1,5,4,2]
    time = timer(bubble_sort)(num)
    print(time)

timer是计算函数运行计时的函数,详见《Python——关于算法与数据结构》有不记得的小伙伴可以再瞅一眼哈。

运行结果如下:

[3, 1, 5, 4, 2, 6]

[1, 3, 4, 2, 5, 6]

[1, 3, 2, 4, 5, 6]

[1, 2, 3, 4, 5, 6]

[1, 2, 3, 4, 5, 6]

[1, 2, 3, 4, 5, 6]

6.100000000003325e-05

改进后的coding

上面的代码测试了一下,你会发现的确是时间复杂度中分析的,运行了6个循环(输出结果我直接打印了出来),可是有个问题,不知道你是否有发现。就是,最后3行是一模一样,都是排好序的,换句话说,就是有2行是无用功。

那是否有办法改进一下呢?of course

思路就是:

如果运行到某一轮,所有数字都不需要互换位置,也就是if num[i]>num[i+1]: 该轮中的每一次if条件都没发生,那么,排序就完成了,就可以提前结束while循环,输出结果了。so,只需要加一个flag即可,改进后的代码如下:

#!/usr/bin/env python3.6
# -*- coding: utf-8 -*-
# @Time    : 2019-03-24 18:39
# @Author  : Ed Frey
# @File    : bubble_sort.py
# @Software: PyCharm
from time import clock

def timer(f):
    def _f(*args):
        t0 = clock()
        f(*args)
        return clock() - t0
    return _f

def func(date):
    for i in range(10):
        print(i**3,date)


def bubble_sort(num:list):
    lenth = len(num)
    while lenth:
        flag = False
        for i in range(lenth-1):
            if num[i]>num[i+1]:
                num[i],num[i+1] = num[i+1],num[i]
                flag = True    
        if flag == False:
            break
        lenth -= 1
        print(num)
    return num

if __name__ == '__main__':
    num = [6,3,1,5,4,2]
    time = timer(bubble_sort)(num)
    print(time)
运行结果如下:

[3, 1, 5, 4, 2, 6]

[1, 3, 4, 2, 5, 6]

[1, 3, 2, 4, 5, 6]

[1, 2, 3, 4, 5, 6]

5.099999999996774e-05

运行时间上,改进后的代码,是少了一点点。数组元素只有6个,可能不是很明显,如果换成一个很大的数组,就显而易见了。

本文分享自微信公众号 - 奔跑的键盘侠(runningkeyboardhero)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-03-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • len(x) 击败 x.len(),从内置函数看 Python 的设计思想

    它们预先定义在内置命名空间中,开箱即用,所见即所得。Python 被公认是一种新手友好型的语言,这种说法能够成立,内置函数在其中起到了极关键的作用。

    Crossin先生
  • 程序员编程十大原则,学不会就是真小白

    大多数情况下,文档不用于通信,它用于记录。大多数要求仍然通过口头交流传达,但文件没有记录,后续工作很容易!

    秃头哥编程
  • Redis常用技术-----使用Lua语言

    Redis命令的计算能力并不算很强大,使用Lua语言则可以在很大程度上弥补Redis的这个不足。在Redis中,执行Lua语言是原子性,也就是说Redis执行L...

    秃头哥编程
  • 面试常考-链表反转解析

    你是否有过这种体会:看别人的代码,当时看得很明白了,但是,过段时间,自己却怎么都写不出来?这是怎么回事,可能我们也清楚。别人的思维你是无法拷贝的,形成之前不具备...

    石晓文
  • Java开发神器Lombok的安装与使用

    项目中经常使用bean,entity等类,绝大部分数据类类中都需要get、set、toString、equals和hashCode方法,虽然eclipse和id...

    秃头哥编程
  • 如何通过Java反射获取泛型类型信息

    关于Java泛型,很多人都有一个误解,认为Java代码在编译时会擦除泛型的类型,从而在运行时导致没法访问其类型,这其实并不完全正确,因为有一部分泛型信息是可以在...

    我是攻城师
  • Redis内存回收策略

    Redis会因为内存不足而产生错误,也会因为回收过久而导致系统长期的停顿,因此了解掌握Redis的回收策略十分重要。当Redis的内存达到规定的最大值时,可以进...

    秃头哥编程
  • Flash如何模拟EEPROM

    很多的MCU控制器不带有片上EEPROM,但是我们有时候鉴于成本的考虑又不想外扩EEPROM,所以经常用Flash来模拟EEPROM存储,但是Flash都是块擦...

    用户1605515
  • 数据库之索引总结

    索引在数据库中可以说是相当重要的一块知识点了,也是面试经常被问的,这篇文章就总结一下索引相关的知识点,包括索引的底层实现原理,索引的分类,最左匹配原则等。

    秃头哥编程
  • Fortran如何实现矩阵与向量的乘法运算

    矩阵是二维数组,而向量是一维数组,内置函数matmul不能实现矩阵与向量的乘法运算。在这一点Fortran不如matlab灵活。

    fem178

扫码关注云+社区

领取腾讯云代金券