算法学习笔记(三):冒泡排序和归并排序

(一)    冒泡排序

冒泡排序的作用就是反复交换相邻未按次序排列的数据。

 1 #冒泡排序实现,升序版本
 2 def bubbleSort(data):
 3     # 例如:data = [3,2,1], 很明显循环检查 data[0] > data[0+1]  data[1] > data[1+1] 这2个表达式是否成立就行了
 4     # 不需要也不可能去检查 data[2] > data[2+1]是否成立,所以第一重for循环的执行次数是列表长度 - 1
 5     for i in range(len(data)-1):
 6         # 第二重for循环每执行一轮都会排好一个数据,所以下一轮的执行次数在这次的基础上-1(即-i)
 7         #不减这个i不影响最终的排序结果,就是会运行很多没必要执行的循环,因为已经排好序的数据还一直在比较
 8         for j in range(len(data)-1-i):
 9             if data[j] > data[j+1]:
10                 data[j],data[j+1] = data[j+1],data[j] #交换相邻的数据
11                 print(j,data)#这个print是为了看输出,便于理解加上的,实际可以去掉
12     return data
13 
14 A = [11,8,7,3,1]
15 
16 
17 print(bubbleSort(A))

看下面这张图,不难发现,第二重for循环每一轮循环结束后都会排好一个数据

第一轮结束后是:[8, 7, 3, 1, 11],不难发现,11是排序好了的,所以第二轮的循环次数在这次的基础上-1就行了,即len(data)-1-i

第二轮结束后是:[7, 3, 1, 8, 11],不难发现,8,11是排序好了的,所以第三轮的循环次数在这次的基础上-1就行了,即len(data)-1-i。后面都是一样的道理

第三轮结束后。。。。

第四轮结束后。。。。

降序版本
 1 #冒泡排序实现,降序版本
 2 def bubbleSort(data):
 3     for i in range(len(data)-1):
 4         for j in range(len(data)-1-i):
 5             if data[j] < data[j+1]:
 6                 data[j],data[j+1] = data[j+1],data[j] #交换相邻的数据
 7     return data
 8 
 9 A = [3,2,23,11,8,6,5,10,12,15]
10 
11 
12 print(bubbleSort(A))

(二)    归并排序

分为2个过程 :1、分割 2、归并

例如:对列表[5,2,4,7,1,3,2,6] 进行归并排序,过程是这样的

(1)分割:将列表分割,直到列表长度为1,然后开始归并

(2)归并:

 1 #分割数据
 2 def mergeSort(A):
 3     #列表长度等于1时,停止分割,返回该列表
 4     if len(A) == 1:
 5         return A
 6     else:
 7         # //运算符返回商的整数部分,例如3//2 ,返回的就是1
 8         #获取列表元素中间的索引
 9         mid = len(A) // 2
10         left = A[:mid]#截取(列表)索引0到mid之间的数据(不包括索引为mid的数据)
11         right = A[mid:] #截取(列表)索引mid之后的所有数据(包括索引为mid的数据)
12         #递归调用自身继续分割,直到列表长度为1为止
13         L = mergeSort(left)
14         R = mergeSort(right)
15     #调用merge合并数据
16     return merge(L,R)
17 
18 #合并数据
19 def merge(L,R):
20     result = []
21     while len(L) > 0 and len(R)>0:
22         #判断哪个数据比较大,将比较小的数据添加到result列表中
23         if L[0] <= R[0]:
24             #pop(0)是从列表删除索引为0的数据并返回
25             result.append(L.pop(0))
26         else:
27             result.append(R.pop(0))
28     #其中一个列表的数据为空后会退出while循环,将另一个列表的数据直接添加到result中
29     result.extend(L)
30     result.extend(R)
31     return result
32 
33 A = [5,2,4,7,1,3,2,6]
34 
35 
36 print(mergeSort(A))

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏web前端教室

重学javascript 红皮高程(3)

继续啊,继续JS基础知识补全之路。 昨天说到JS的几种数据类型,像我这种脑子不太好使,记不清JS共有几种对象的人,可以这么记,JS这东西根本不支持自定义类型,所...

2249
来自专栏软件开发 -- 分享 互助 成长

访问者模式

一、简介 1、访问者模式表示一个作用于某对象结构中各元素的操作。它使你可以在不改变各元素的类的前提下定义作用于这些元素的新操作。 2、模式中的成员角色 访问者(...

1845
来自专栏青青天空树

c/C++二进制运算符

  1.  &  :  与操作.作用于两个二进制数,当然也可以对整型数据进行操作(当两边为整型数据会自动转化为二进制数).二进制与用来对位进行置零或者复位.如果...

892
来自专栏Golang语言社区

Golang语言之异常处理

在编写Go语言代码的时候,我们应该习惯使用error类型值来表明非正常的状态。作为惯用法,在Go语言标准库代码包中的很多函数和方法也会以返回error类型值来表...

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

剑指OFFER之用两个栈实现队列(九度OJ1512)

题目描述: 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 输入: 每个输入文件包含一个测试样例。 对于每个测试样例,第一...

2075
来自专栏老九学堂

十七个C语言新手编程时常犯的错误及解决方式

C编译的程序对语法检查并不像其它高级语言那么严格,这就给编程人员留下“灵活的余地”,但还是由于这个灵活给程序的调试带来了许多不便,尤其对初学C语言的人来说,经常...

3247
来自专栏java闲聊

Mybatis 初探,动态代理

在项目中经常使用Mybatis框架作用DAO层,但是你真的对Mybatis的原理清楚吗?带着这个疑惑我们来实现一个简单的动态代理,本次了解的是接口实现动态代理,...

2106
来自专栏web前端教室

重学javascript 红皮高程(2)

为了送礼三八女王节,今晚跟同学一起喝酒去了。更新的有点晚,哈哈。。 让我们继续重新温习JS高程,今天来复习下基本概念。 JS它的语法是区分大小写地,并且函数名不...

1948
来自专栏郭耀华‘s Blog

网易笔试编程题:被3整除

1472
来自专栏進无尽的文章

编码篇-Block里面的小天地

Block是iOS4.0+ 和Mac OS X 10.6+ 引进的对C语言的扩展,用来实现匿名函数的特性。 通常来说,block都是一些简短代码片段的封装,适...

1232

扫码关注云+社区

领取腾讯云代金券