(一) 冒泡排序
冒泡排序的作用就是反复交换相邻未按次序排列的数据。
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))