Python之排序算法:快速排序与冒泡排序

Python之排序算法:快速排序与冒泡排序

转载请注明源地址:http://www.cnblogs.com/funnyzpc/p/7828610.html

入坑(简称IT)这一行也有些年头了,但自老师讲课提过排序算法后几乎再也没写过排序算法,当然这也没有什么问题,实际的排序大多是将数据从数据库取出来前在数据库中就已经做好排序了,当然这个排序是SQL范畴的,如果真的需要在代码中排序也有对应的工具类来处理,就比如有Java中有Array.sort()来排列Array(数组类型),功能虽说有限制,但也免去了撸码的时间,嗯,不用写的大好处就是减少了开发时间,当然也增加了喝咖啡、网购的时间~

闲言多废话,先展示下快速排序的动态图再出代码,方便理解:

(上图是从维基百科中抓取的,包括本节所讲所的冒泡排序也是维基百科的)

  嗯,酷酷的时间到了

,先我大概讲下快速排序

A>先取一个数(一般是第一个数)作为参照的基准值

    B>将待排序的数组分两边,一左一右分别指向数组的两边

    C>左右两边分别向中间移,所指的数值大于基准值的向基准值右边放(如果是右边所指的值就挪动指向的位置,值不动),左边也一样

    D>将基准位置两边的值分别排序(一般是递归调用)

好了,以上大概就是快速排序的的一半步骤,如有不懂之处,建议顺着代码来推测快速排序的整个过程,并不难

 1 #!/usr/bin/env Python
 2 #快速排序法
 3 def quickSort(arr,_l,_r):
 4     l,r,t=_l,_r,0
 5     if l <= r:
 6         t=arr[_l]   #基准参数
 7         while(l<r):
 8             #当右边的值大于基准参数时,右值向左挪一(位置和值)
 9             while l<r and arr[r]>=t:
10                 r=r-1
11             arr[l]=arr[r]   #右值挪到左值的位置
12             # 当左边的值小于基准参数时,右值向左挪一(位置和值)
13             while l<r and arr[l]<=t:
14                 l=l+1
15             arr[r]=arr[l]   #左值放入右值的位置
16         '''
17             当前一轮排完后将基准参数放入
18             将基准值左右两边的数值分别放入排序(递归调用)
19         '''
20         arr[r]=t #基准参数归位
21 
22         quickSort(arr,_l,l-1) #基准位置左侧数据排序
23         quickSort(arr,l+1,_r) #基准位置右侧数据排序
24 
25 i=[23,1,6,77,8,-11,100,11.1,99,24,21]
26 print ("排序之前")
27 print (i)
28 print ("排序之后")
29 quickSort(i,0,len(i)-1)
30 print (i)
31 
32 ==========以下是控制台输出===========
33 
34 排序之前
35 [23, 1, 6, 77, 8, -11, 100, 11.1, 99, 24, 21]
36 排序之后
37 [-11, 1, 6, 8, 11.1, 21, 23, 24, 77, 99, 100]

嗯~,快速排序完毕,先展示下冒泡排序的动态图,密集恐惧症者勿入

结合着图,冒泡排序的过程大致是这样子的:

  A>取待排序数组中的一个值(一般是第一个值)作为基准值依次与其它所有数值比较

  B>大于基准值的直接略过,小于基准值的与基准值交换位置

额~,还是用代码说话还是比较好一些吧~

 1 #!/usr/bin/env Python
 2 
 3 #冒泡排序法
 4 def bubleSort(arr):
 5     for k in range(len(arr)):
 6         temp = arr[k]   #临时值,用于交换
 7         for j in range(k+1,len(arr)):
 8             '''
 9                 若值比基准值小则将基准值与当前值交换位置
10             '''
11             if arr[j]<arr[k]:
12                 temp=arr[k]
13                 arr[k]=arr[j]
14                 arr[j]=temp
15                 continue;   #这里可有可无
16 
17 i=[23,1,6,77,8,-11,100,11.1,99,24,21]
18 
19 print ("排序前")
20 print (i)
21 print ("排序后")
22 bubleSort(i)
23 print (i)
24 
25 ==========控制台输出============
26 排序前
27 [23, 1, 6, 77, 8, -11, 100, 11.1, 99, 24, 21]
28 排序后
29 [-11, 1, 6, 8, 11.1, 21, 23, 24, 77, 99, 100]

既然是Python,当然Python中对于数组也内置了一键排序算法:

1 ii=[23,1,6,77,8,-11,100,11.1,99,24,21]
2 ii.sort()    #数组内置sort方法排序
3 print ("ii",ii)
4 ij=[23,1,6,77,8,-11,100,11.1,99,24,21]
5 ij=sorted(ij) #外部方法排序(相当于工具类)
6 print ("ij",ij)

既然Python已经提供了排序方法,还要白忙活一气,是不是很悲伤?

以上排序代码真实可信,均为本猿一行行码出,写得十分痛苦

,同时如有遗漏及错误之处敬请提出~

That's All,现在是 2017-11-19 16:03:22 (周五),小学生都忙着赶作业,我也该撤了

下一节是 “Django” 框架搭建,如兴趣的记得点关注?

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大史住在大前端

javascript基础修炼(2)——What's this(上)

this是javascript关键字之一,是javascript能够实现面向对象编程的核心概念。用得好能让代码优雅高端,风骚飘逸,用不好也绝对是坑人坑己利器。我...

751
来自专栏码云1024

RandomAccessFile&IO流&排序&方法论

2767
来自专栏斑斓

当函数成为一等公民时,设计模式的变化

GOF提出的设计模式,其本质思想是封装变化。故而,创建型模式封装的是对象创建的变化,结构型模式封装的是对象之间的协作与组合结构,行为型模式则封装了对象行为的变化...

3065
来自专栏magicsoar

Effective Modern C++翻译(6)-条款5:auto比显示的类型声明要更好

    在概念上说,auto关键字和它看起来一样简单,但是事实上,它要更微妙一些的。使用auto会让你在声明变量时省略掉类型,同时也会防止了手动类型声明带来的正...

19110
来自专栏影子

Python之排序算法:快速排序与冒泡排序

35416
来自专栏数据结构与算法

P1049 装箱问题

题目描述 有一个箱子容量为V(正整数,0<=V<=20000),同时有n个物品(0<n<=30,每个物品有一个体积(正整数)。 要求n个物品中,任取若干个装入箱...

2805
来自专栏Golang语言社区

第九节 Go语言循环语句

干货来了!!!为了让更多的小伙伴喜欢Golang、加入Golang之中来,Golang语言社区发起人彬哥联合业界大牛共同推出了Go语言基础、进阶、提高课程,目前...

792
来自专栏写代码的海盗

我们是80后 golang入坑系列

现在这个系列,已经开始两极分化了。 点赞的认为风格轻松,看着不困。反之,就有人嫌写的罗里吧嗦,上纲上线。所以善意提醒,里面不只是技术语言,还有段子。专心看技术的...

3407
来自专栏Java帮帮-微信公众号-技术文章全总结

第八天 自定义类型方法集合混合使用【悟空教程】

1938
来自专栏Albert陈凯

Scala简介:面向对象和函数式编程的组合

Scala简介 “Scala是一门现代的多范式编程语言,志在以简练、优雅及类型安全的方式来表达常用编程模式。它平滑地集成了面向对象和函数语言的特性。” Sc...

2626

扫码关注云+社区