Python数据结构（排序）
最近好多天都没有更新，主要是在学习Python数据结构，哎，一言难尽，大一C语言数据结构没有好好学，导致现在几乎从头开始，学习算法的话，希望大家一定好好掌握python语言基础，没有基础的话，可能学习很困难，然后后面的话有很多算法，希望大家不仅仅是理解，更多是完全掌握，这样才能在以后的面试考试中对自己学的代码架构理解程度更高。
补充一点，我在学习数据结构时，又在前面的Python笔记中加了很多笔记，但是因为记录的比较乱，后面我会整理一下发出去，但是具体的时间待定，毕竟补充的也很少，哪里不懂直接私信我就好了。
目录
3. 排序
-
排序：将一组“无序”的记录序列调整为“有序”的记录序列
-
列表排序
-
输入：列表
-
输出：列表
-
-
升序与降序
-
内置排序函数：sort() sorted()
常见的排序算法
冒泡排序 选择排序 插入排序
快速排序 堆排序 归并排序
希尔排序 计数排序 基数排序
3.1 冒泡排序（Buddle Sort）
-
列表每两个相邻的数，如果前面的比后面大，则交换这两个数
-
一趟排序完成后，则无序区减少一个数，有序区减少一个数
-
时间复杂度 O(n2)
# 升序
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 ）
简单的排序
-
缺点：
-
产生两个列表，占内存大
-
时间复杂度O(n2)
-
# 简单的选择排序
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)-
时间复杂度：O(n2)
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)