Python代码实现 冒泡 选择 插入 希尔 归并 快速 排序 （思想与注释）

希尔 归并 快速 排序 （思想与注释）"/>

Python代码实现 冒泡 选择 插入 希尔 归并 快速 排序 （思想与注释）

冒泡排序

思想 

两层循环 外层控制整体循环次数 内层循环每一次找出最大值或最小值 依次类推

def bubble_sort(li):for i in range(len(li)-1): #整个列表循环次数for j in range(len(li)-1-i): # 长度-1 - i此时是循环次数的下标 每次都减一if li[j] > li[j+1]: # 如果当前位置参数比后一个大就交换li[j],li[j+1] = li[j+1],li[j] # 交换return li

时间复杂度

• 最优时间复杂度：O(n)
• 最坏时间复杂度：O(n2)
• 稳定性：稳定

插入排序

思想

插入排序 插曲排序的思想也是两层循环有两个游标 1和0比 如果小交换 依次类推 外层循环也是控制次数

def insert_sort(alist):# 从第二个位置，即下标为1的元素开始向前插入for i in range(1, len(alist)):# 从第i个元素开始向前比较，如果小于前一个元素，交换位置for j in range(i, 0, -1):if alist[j] < alist[j-1]:alist[j], alist[j-1] = alist[j-1], alist[j]

时间复杂度

• 最优时间复杂度：O(n)
• 最坏时间复杂度：O(n2)
• 稳定性：稳定

选择排序

思想

 其实也差不多也是两层循环 内层循环找到最小值 然后与下标为0交换

def selection_sort(alist):n = len(alist)# 需要进行n-1次选择操作for i in range(n-1):# 记录最小位置min_index = i# 从i+1位置到末尾选择出最小数据for j in range(i+1, n):if alist[j] < alist[min_index]:min_index = j# 如果选择出的数据不在正确位置，进行交换if min_index != i:alist[i], alist[min_index] = alist[min_index], alist[i]

时间复杂度

• 最优时间复杂度：O(n2)
• 最坏时间复杂度：O(n2)
• 稳定性：不稳定

shell 排序

思想

其实就是插入排序的升级版 只是多了一个 gep 间隔值 据说用数学算到极致 时间复杂度O(n^1.3)次方

def shell_sort(li):# 先取出 gep值gep = len(li) // 2 # 取整除 python3 里需要// 2不需要# 控制gep 值while gep > 0:# 外层循环控制循环整体次数for i in range(gep,len(li)):# 此时gep循环就是+1+1+1while i > 0:if li[i] < li[i-gep]:# 此时开始比较li[i],li[i-gep] = li[i-gep],li[i]i -= gepelse:breakgep //= 2return li

时间复杂度

• 最优时间复杂度：根据步长序列的不同而不同
• 最坏时间复杂度：O(n2)
• 稳定性：不稳定

归并排序

思想

      就是先递归分解数组，再合并数组

def merge_sort(alist):if len(alist) <= 1:return alist# 二分分解num = len(alist)/2left = merge_sort(alist[:num])right = merge_sort(alist[num:])# 合并return merge(left,right)def merge(left, right):'''合并操作，将两个有序数组left[]和right[]合并成一个大的有序数组'''#left与right的下标指针l, r = 0, 0result = []while l<len(left) and r<len(right):if left[l] < right[r]:result.append(left[l])l += 1else:result.append(right[r])r += 1result += left[l:]result += right[r:]return result

时间复杂度

• 最优时间复杂度：O(nlogn)
• 最坏时间复杂度：O(nlogn)
• 稳定性：稳定

快速排序

思想 （标准的用性能换时间）

快速排序 两个游标 一个base == midvalue  开始游标和结束游标  右边游标向左移动 碰到 比mide小的 与
开始下标交换  开始下标 向右移动 遇到比 mide 大的 与 结束游标 交换 当 开始与结束 下标相遇 就是mide的位置现在mide 左侧 一定比mide小 右侧的比mide大  这时递归调用自己 两次 一次 用快排计算 左边的值
一次计算右边的值 但是切记不可使用切片（归并是切片）  因为要操作的是同一个列表

def quick_sort(alist,first,last):# 控制递归值if first >= last:return# 需要比较的值mid_value = alist[first]# 从左到又比较mid_value下标start_index = first# 从右到左end_index = last# 外层循环while start_index < end_index:# end_ndex向右移动 条件是 开始必须比结束小 and 每次移动的值比base大while start_index < end_index and alist[end_index] >= mid_value:# 每次向左移动 减一个下标end_index -= 1# 如果碰到条件不允许 赋值与 startalist[start_index] = alist[end_index]# start_inde 向左移动 条件同理while start_index < end_index and alist[start_index] < mid_value:# start 每次加一个下标start_index += 1# 交换值alist[end_index] = alist[start_index]# 直到 mid 左边是 都是比他小的 右边都是比他大的# 既然退出循环那就证明mid的位置值已经找到 看你开心 现在 start和end的值已经重合# 因为上面有多余常数已经交换alist[start_index] = mid_value# 现在左右两边已经分开 调用递归 分别完成快速排序# 有个坑 操作的是同一列表！！！！## 递归左边列表quick_sort(alist,first,start_index-1) # alist first, start_inde-1# 递归右边列表quick_sort(alist,start_index+1,last) # alist  start_index+1 ,len(li)-1

时间复杂度

• 最优时间复杂度：O(nlogn)
• 最坏时间复杂度：O(n2)
• 稳定性：不稳定