下载安卓APP箭头
箭头给我发消息

客服QQ:3315713922

教你用python实现冒泡排序

作者:课课家教育     来源: http://www.kokojia.com点击数:7452发布时间: 2016-05-06 11:03:45

标签: python冒泡排序python排序python

大神带你学编程,欢迎选课

  所谓冒泡排序,其实是一种在计算机领域里较简单的排序算法。思想就是从数组的第一个元素一个个跟在后面,再挪到相应的位置上去。本文教大家的是利用Python程序语言编写冒泡排序,下面我们一起来看看吧。

  为了用python实现各种排序,首先我先创建一个大小为5000的随机列表,公式的写法大概如下:

source_list = [random.randint(1, 2000) for i in range(5000)]

  然后再写一个装饰器,打印排序的耗时和排好序的新列表,装饰器如下:

  教你用python实现冒泡排序_python冒泡排序_python排序_python_课课家

  下面我们先来做一个冒泡排序,看到这里一定有人不知道什么是冒泡排序,理科出身的同学应该容易理解,就是比较相邻的元素。如果第一个比第二个大,就交换他们两个,对第0个到第n-1个数据做同样的工作。这时,最大的数就“浮”到了数组最后的位置上。以上就是冒泡排序的概念,这下你该知道什么叫冒泡排序了吧。

  针对所有的元素重复以上的步骤,除了最后一个,持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。说再多也不及你做一遍来的好,代码如图。

  附上代码:

  冒泡排序代码

  终端输出为:bubble_sort 0.626999855042 [1, 1, 1, 1, 1, 1, 2, 2, 2, 4, 5, 6, 6,...

  冒泡很简单,但是大家都知道效率并不高,看到输出结果你不难发现其循环效果太明显了,而且python的for循环效率更是恶心,双重循环的次数又那么多。好在平时并不用冒泡,只是为了理解冒泡排序。

  下面我们看看选择排序,什么是选择排序呢?就是在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的后面。以此类推,直到所有元素均排序完毕。

  代码附上:

  python冒泡排序的代码

  终端输出为:select_sort 0.25200009346 [1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 6,...

  我们用选择排序和冒泡排序做个比较,不难发现选择排序效率远远高于冒泡排序,从代码上不难理解冒泡排序的交换次数远远多于选择排序的交换次数。这样一比较,选择排序比冒泡排序简洁多了。

  再来看一个扩展,利用python的语言特色 min 和list.remove() 完成选择排序。

  我们用选择排序和冒泡排序做个比较,不难发现选择排序效率远远高于冒泡排序。

  终端输出为:select_sort1 0.133999824524 [1, 2, 2, 3, 3, 3, 4, 4, 5, 6, 6,...

  python的 min 和list.remove() 组合的效率更是优秀,实操起来也不难,有兴趣的朋友有时间可以试试啊。

  下面来看一个插入排序,什么是插入排序呢?来看一下插入排序的步骤:

  1,从第一个元素开始,该元素可以认为已经被排序。

  2,取出下一个元素,在已经排序的元素序列中从后向前扫描。

  3,如果被扫描的元素(已排序)大于新元素,将该元素后移一位。

  4,重复步骤3,直到找到已排序的元素小于或者等于新元素的位置,将新元素插入到该位置后。

  5,重复步骤2~5。

  代码如下:

  python冒泡排序

  终端输出的结果:insert_sort 0.242000102997 [1, 4, 4, 6, 6, 6, 6, 7, 9,...

  再来演示一个快速排序,什么是快速排序呢?上面演示了冒泡排序、选择排序、插入排序,现在讲快速排序,希望大家不要混淆了。快速排序是从数列中挑出一个元素作为基准数。分区过程,将比基准数大的放到右边,小于或等于它的数都放到左边。再对左右区间递归执行第二步,直至各区间只有一个数。

  代码送上:

  python快速排序的编码

  看一下终端的输出:qu_sort 0.00799989700317 [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, ...

  你可以从中对比发现,快速排序的效率超级高的,所以小编认为,数据量大的时候用快排是比较好的,唯一担心的就是递归的深度,所以结合实际情况吧。有兴趣学习的朋友可以把代码优化一下,然后拿出来给大家分享学习。

  本文讲述用python实现冒泡排序、选择排序等等,也罗列了详细地编码共大家参考学习。你看到后是不是觉得冒泡排序挺有趣,其他类型的排序也很好玩,有空大家可以用python试试。

赞(16)
踩(2)
分享到:
华为认证网络工程师 HCIE直播课视频教程