|
最近好多天都没有更新，主要是在学习Python数据结构，哎，一言难尽，大一C语言数据结构没有好好学，导致现在几乎从头开始，学习算法的话，希望大家一定好好掌握python语言基础，没有基础的话，可能学习很困难，然后后面的话有很多算法，希望大家不仅仅是理解，更多是完全掌握，这样才能在以后的面试考试中对自己学的代码架构理解程度更高。
? ? ? ? 补充一点，我在学习数据结构时，又在前面的Python笔记中加了很多笔记，但是因为记录的比较乱，后面我会整理一下发出去，但是具体的时间待定，毕竟补充的也很少，哪里不懂直接私信我就好了。
目录
3. 排序
常见的排序算法
3.1 冒泡排序（Buddle Sort）
3.2 选择排序（select sort ）
3.3 插入排序（insert sort）
3.4 快速排序(quick sort)
3. 排序
常见的排序算法
冒泡排序? ? ? ? 选择排序? ? ? ? 插入排序
快速排序? ? ? ? 堆排序? ? ? ? ? ? 归并排序
希尔排序? ? ? ? 计数排序? ? ? ? 基数排序
3.1 冒泡排序（Buddle Sort）
# 升序
?def bubble_sort(li):
? ? ?for i in range(len(li) - 1): # 循环遍历 n-1 躺
? ? ? ? ?for j in range(len(li)-i-1):
? ? ? ? ? ? ?if li[j] > li[j+1]: ? ? ? ? ? ? # 升序
? ? ? ? ? ? ? ? ?li[j],li[j+1] = li[j+1],li[j] # 交换两个数的位置
? ? ? ? ? ? ? ? ?pass
? ? ? ? ? ? ?pass
? ? ? ? ?print(li)
?# 降序
?def bubble_sort2(li):
? ? ?for i in range(len(li) - 1): # 循环遍历 n-1 躺
? ? ? ? ?for j in range(len(li)-i-1):
? ? ? ? ? ? ?if li[j] < li[j+1]: ? ? ? ? ? ? ? ? # 降序
? ? ? ? ? ? ? ? ?li[j],li[j+1] = li[j+1],li[j] # 交换两个数的位置
? ? ? ? ? ? ? ? ?pass
? ? ? ? ? ? ?pass
? ? ? ? ?print(li)
??
?# 升级版，减少排序次数，如果前面已经有序的话，不再排序
??
?def bubble_sort(li):
? ? ?for i in range(len(li) - 1): # 循环遍历 n-1 躺
? ? ? ? ?exchange = False # 无交换的话返回False
? ? ? ? ?for j in range(len(li)-i-1):
? ? ? ? ? ? ?if li[j] > li[j+1]: ? ? ? ? ? ? # 升序
? ? ? ? ? ? ? ? ?li[j],li[j+1] = li[j+1],li[j] # 交换两个数的位置
? ? ? ? ? ? ? ? ?exchange = True # 交换的换返回True
? ? ? ? ?print(li)
? ? ? ? ?if not exchange: # 如果exchange没有变化，证明排序完成，不需要执行下面的循环
? ? ? ? ? ? ?return
?li = [1,2,3,4,5,6,7,9,8]
?# print(li)
?bubble_sort(li)
3.2 选择排序（select sort ）
简单的排序
# 简单的选择排序
??
?def select_sort_simple(li):
? ? ?li_new = []
? ? ?for i in range(len(li)):
? ? ? ? ?min_val = min(li) #找到最小值
? ? ? ? ?li_new.append(min_val) # 添加到新列表中
? ? ? ? ?li.remove(min(li)) # 再旧列表中删除最小值
? ? ? ? ?pass
? ? ?return li_new
?li = [1,2,4,3,7,9,6,8]
?print(select_sort_simple(li))
# 正常的选择排序
?def select_sort(li):
? ? ?for i in range(len(li)-1): # i 表示第几躺
? ? ? ? ?min_loc = i # 最小值的位置
? ? ? ? ?for j in range(i+1,len(li)):
? ? ? ? ? ? ?if li[j] < li[min_loc]:
? ? ? ? ? ? ? ? ?min_loc = j
? ? ? ? ?if min_loc != i:
? ? ? ? ? ? ?li[i], li[min_loc] = li[min_loc], li[i]
? ? ? ? ?# print(li)
?li = [5,8,9,6,4,2,3]
?select_sort(li)
?print(li)
3.3 插入排序（insert sort）
-
初始时手里(有序区)只有一张牌 -
每次从(无序区)摸一张牌，插入到手里已有牌的位置 -
时间复杂度：O(n2)
def insert_sort(li):
? ? ?for i in range(1,len(li)): ?# i 表示摸到牌的下标
? ? ? ? ?tmp = li[i]
? ? ? ? ?j = i - 1 # j指的是手里牌的下标
? ? ? ? ?while j >= 0 and li[j] > tmp:
? ? ? ? ? ? ?li[j+1] = li[j]
? ? ? ? ? ? ?j -= 1 # j往右移
? ? ? ? ?li[j+1] = tmp
?li = [1,4,2,5,3,6]
?print(insert_sort(li))
?print(li)
3.4 快速排序(quick sort)
?def partition(li,left,right):# 归位函数
? ? ?tmp = li[left]
? ? ?while left < right:
? ? ? ? ?while left < right and li[right] >= tmp: # 从右边找到比tmp小的数
? ? ? ? ? ? ?right -= 1 # 往左移一位
? ? ? ? ? ? ?pass
? ? ? ? ?li[left] = li[right] # 把右边的值写到左边的空位上
? ? ? ? ?while left < right and li[left] <= tmp:
? ? ? ? ? ? ?left += 1
? ? ? ? ? ? ?pass
? ? ? ? ?li[right] = li[left] # 把左边的值写到右边的空位上
? ? ? ? ?# print(li)
? ? ?li[left] = tmp # 把tmp归位
? ? ?return left
?li = [5,7,4,6,3,2,9,8]
?partition(li,0,len(li)-1)
?print(li)
?# 全部快速排序
?def partition(li,left,right):# 归位函数
? ? ?tmp = li[left]
? ? ?while left < right:
? ? ? ? ?while left < right and li[right] >= tmp: # 从右边找到比tmp小的数
? ? ? ? ? ? ?right -= 1 # 往左移一位
? ? ? ? ? ? ?pass
? ? ? ? ?li[left] = li[right] # 把右边的值写到左边的空位上
? ? ? ? ?while left < right and li[left] <= tmp:
? ? ? ? ? ? ?left += 1
? ? ? ? ? ? ?pass
? ? ? ? ?li[right] = li[left] # 把左边的值写到右边的空位上
? ? ? ? ?# print(li)
? ? ?li[left] = tmp # 把tmp归位
? ? ?return left
??
?def quick_sort(li,left,right):
? ? ?if left < right: # 至少两个元素
? ? ? ? ?mid = partition(li,left,right)
? ? ? ? ?quick_sort(li,left,right-1)
? ? ? ? ?quick_sort(li,mid+1,right)
??
?li = [5,7,4,6,3,2,9,8]
?quick_sort(li,0,len(li)-1)
?print(li)
-
时间复杂度 O(nlogn) -
最坏情况：当列表为倒叙时，时间复杂度为O(n2)
|