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 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

【插件开发】—— 6 SWT 复杂控件使用以及布局

前文回顾: 1 插件学习篇 2 简单的建立插件工程以及模型文件分析 3 利用扩展点,开发透视图 4 SWT编程须知 5 SWT简单控件的使用与布局搭...

2349
来自专栏菩提树下的杨过

Silverlight:利用异步加载Xap实现自定义loading效果

关键点: 1.利用WebClient的DownloadProgressChanged事件更新下载进度 2.下载完成后,分析Xap包的程序集Assembly信息 ...

18610
来自专栏自由而无用的灵魂的碎碎念

小项目分享---混色器

编写代码的同志们一般懂美术的就少了,偶也是,什么色轮、三维加色等等。虽然看过一些书籍(如内田广由纪的《配色基础原理》),不过还是一知半解的。

973
来自专栏田超学前端

【微信小程序】c# 实现获取openid、session_key 服务端

5240
来自专栏菩提树下的杨过

基于sliverlight + wcf的web 文字版IM 示例

演示地址: http://task.24city.com/default.html 预览界面: ? 一、布局 采用Grid布局,5行2列 第一行:为登录/注册信...

3226
来自专栏张善友的专栏

通过SmtpClient发送Exchange会议邮件

看到C#中调用Outlook API 发起会议 ,这个完全可以用SMTP方式实现的,下面我的项目中使用的代码: 对于.NET而言,从2.0开始,发邮件已经是一件...

1949
来自专栏c#开发者

xmldocument内嵌入另一个xmldocument,xmlnode的方法

string xmlstr1 = @"<root><head>myHead</head><body></body></root>"; s...

2725
来自专栏跟着阿笨一起玩NET

使用延迟的FileSystemWatcher来避免重复触发事件

  程序里需要监视某个目录下的文件变化情况: 一旦目录中出现新文件或者旧的文件被覆盖,程序需要读取文件内容并进行处理;但在实际处理中发现当一个文件产生变化时,C...

912
来自专栏技术之路

sqlserver 的事务和c#的事务

sql的事务 1 sql 2 create database model 3 go 4 use model 5 go 6 create table ...

1929
来自专栏大内老A

开发自己的Data Access Application Block[下篇]

上接:[原创] 我的ORM: 开发自己的Data Access Application Block - Part I 4. Database 下面来介绍重中之重...

2246

扫码关注云+社区