算法学习笔记（三）：冒泡排序和归并排序

（一）冒泡排序

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

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

第三轮结束后。。。。

第四轮结束后。。。。

降序版本

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

（三） 归并排序

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

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

（1）分割：将列表分割，直到列表长度为1，然后开始归并

（2）归并：

#分割数据
 def mergeSort(A):
     #列表长度等于1时，停止分割，返回该列表
     if len(A) == 1:
         return A
     else:
         # //运算符返回商的整数部分，例如3//2 ，返回的就是1
         #获取列表元素中间的索引
         mid = len(A) // 2
         left = A[:mid]#截取（列表）索引0到mid之间的数据（不包括索引为mid的数据）
         right = A[mid:] #截取（列表）索引mid之后的所有数据（包括索引为mid的数据）
         #递归调用自身继续分割,直到列表长度为1为止
         L = mergeSort(left)
         R = mergeSort(right)
     #调用merge合并数据
     return merge(L,R)
 
 #合并数据
 def merge(L,R):
     result = []
     while len(L) > 0 and len(R)>0:
         #判断哪个数据比较大，将比较小的数据添加到result列表中
         if L[0] <= R[0]:
             #pop(0)是从列表删除索引为0的数据并返回
             result.append(L.pop(0))
         else:
             result.append(R.pop(0))
     #其中一个列表的数据为空后会退出while循环，将另一个列表的数据直接添加到result中
     result.extend(L)
     result.extend(R)
     return result
 
 A = [5,2,4,7,1,3,2,6]
 
 
 print(mergeSort(A))