排序介绍
列表排序：将无序列表变成有序列表（升序或降序）
内置排序函数：sort()
常见排序算法：
LB三人组：冒泡排序、选择排序、插入排序
NB三人组：快速排序、堆排序、归并排序
其他排序： 希尔排序、计数排序、基数排序、桶排序
冒泡排序
列表每两个相邻的数，如果前面比后面大，则交换这两个数。（逐一比较）一趟排序完成后，无序区减少一个数，有序区增加一个数。（每一趟都会把无序区的最大数挑出来）
代码关键点：无序区、有序区、趟、无序区的范围
import random
def bubble_sort(li):
for i in range(len(li)-1):
#标志位
exchange = 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
if not exchange:
return #一趟都不用发生交换，表明已经排好序，不用进行多余的步骤
lii = [random.randint(0,10000) for i in range(1000)]
print(lii)
bubble_sort(lii)
print(lii)
选择排序
每趟排序都记录最小的数，将其依次放在前面的位置。
代码关键点：有序区、无序区、无序区最小数的位置
#选择最小的放在一个空列表中
def select_sort_sample(li):
li_new=[]#生成两个列表，占用更多内存;O(n^2)
for i in range(len(li)):
min_val = min(li)
li_new.append(min_val)
li.remove(min_val)
return li_new
li = [2,1,6,9,6,7,3,2,6]
#print(select_sort_sample(li))
def select_sort(li):
for i in range(len(li)-1):
min_loc = i
for j in range(i+1,len(li)):
if li[j] < li[min_loc]:
min_loc = j
li[i],li[min_loc] = li[min_loc],li[i]#将最小的数放在前面，与之交换的元素放在其原来的位置
select_sort(li)
print(li)
插入排序
初始的列表是有序的，每次从无序区中拿出一个数，将其插入到有序的列表中。
def insert_sort(li):
for i in range(1,len(li)):
tmp = li[i]
j = i-1
while j>=0 and li[j]>tmp:#比摸到的牌大的数往后移,j相当于一个小指针
li[j+1] = li[j]
j -= 1
li[j+1] = tmp
li = [2,3,1,3,2,8,3,2,4]
insert_sort(li)
print(li)快速排序
思路：
1.取一个元素p，使其归位；
2.列表被p分成两部分，左边都比p小，右边都比p大（找位置需要用到反向双指针）
3.递归完成排序
##修改递归最大深度
import sys
sys.setrecursionlimit(10000000)
##随机快速排序，避免最坏情况 ##https://blog.csdn.net/The_Shiled/article/details/121777268
def partition(li,left,right):
tmp = li[left]
while left < right:
while left < right and li[right]>=tmp:#从右面找出比tmp小的数
right -= 1#往左走一步
li[left] = li[right]#把右边的值写到左边的空位上
while left < right and li[left] <= tmp:
left += 1
li[right] = li[left]#把左边的值写到右边的空位上
li[left] = tmp#将tmp归位
return left
def quick_sort(li,left,right):
if left < right:
mid = partition(li,left,right)
quick_sort(li,left,mid-1)
quick_sort(li,mid+1,right)堆排序
二叉树：度不超过2的树。每个节点最多有两个子节点。
满二叉树：一个二叉树，如果每一层的节点树都达到最大值，则这个树为满二叉树。
完全二叉树：叶节点只能出现在最下层和次下层，并且最下层的节点都集中在该层的最左边的若干个位置的二叉树。
?二叉树的存储方式有链式存储方式、顺序存储方式。这里采用的是顺序存储方式。
堆：一种特殊的完全二叉树结构。有顺序的
大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大。
小根堆：一棵完全二叉树，满足任一节点都比其孩子节点小。
堆的向下调整：假设节点左右子树都是堆，但自身不是堆。可以通过向下调整变成堆。
堆排序过程：
1.建立堆。
2.得到堆顶元素，此为最大元素。
3.去掉堆顶，将堆最后一个元素放到堆顶，此时可以通过一次向下调整重新使堆有序。
4.堆顶元素为第二大元素。
5.重复步骤3，指导堆变空。
#大根堆
def sift(li,low,high):
'''
li:列表
low:堆的根节点位置
high:堆的最后一个节点的位置
'''
i = low#i最开始指向根节点，之后指向每一子树的根节点 找父节点与子节点的关系
j = 2*i+1#j开始是左孩子
tmp = li[low]#把堆顶存起来
while j <= high:#只要j位置有数
if j+1<= high and li[j+1]>li[j]:#如果右孩子存在且较大
j = j+1#j指向右孩子
if li[j]>tmp:
li[i] = li[j]
i = j #往下看一层
j = 2*i+1
else:
break#结束循环
li[i] = tmp#最后一层了 两次结束循环，都需要把tmp放回来
def heap_sort(li):
n = len(li)
for i in range((n-2)//2,-1,-1):#i表示建堆时调整部分根的下标
sift(li,i,n-1) #设high指最后一层
#建堆完毕
for i in range(n-1,-1,-1):#i指向当前堆的最后一个节点的位置
li[0],li[i] = li[i],li[0]
sift(li,0,i-1)#i-1是新的high
li = [i for i in range(100)]
# li = list(range(100))
import random
random.shuffle(li)
print(li)
# heap_sort(li)
# print(li)
##堆排序的内置代码
import heapq#优先队列 小的先出，或大的先出
heapq.heapify(li)#建堆 小根堆
#heapq.heappop(li)#向外弹出最小元素 升序
lii = []
for i in range(len(li)):
lii.append(li[i])
print(lii)堆排序——topk问题
现在有n个数，设计算法得到前k个大的数。
取列表前k个元素建立一个小根堆，堆顶就是目前第k大的数。
依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略；如果大于堆顶，则将堆顶更换为该元素，并且对堆进行一次调整。
遍历列表所有元素后，倒序弹出堆顶。
def sift(li,low,high):#小根堆
'''
li:列表
low:堆的根节点位置
high:堆的最后一个节点的位置
'''
i = low#i最开始指向根节点，之后指向每一子树的根节点
j = 2*i+1#j开始是左孩子
tmp = li[low]#把堆顶存起来
while j <= high:#只要j位置有数
if j+1<= high and li[j+1]<li[j]:#如果右孩子存在且较小
j = j+1#j指向右孩子
if li[j]<tmp:
li[i] = li[j]
i = j #往下看一层
j = 2*i+1
else:
break#结束循环
li[i] = tmp#最后一层了 两次结束循环，都需要把tmp放回来
def topk(li,k):
heap=li[0:k]
for i in range((k-2)//2,-1,-1):#i表示建堆时调整部分根的下标
sift(li,i,k-1) #设high指最后一层
for i in range(k,len(li)):#遍历
if li[i]>heap[0]:
heap[0] = li[i]
sift(heap,0,k-1)
for i in range(k-1,-1,-1):#出数
heap[0],heap[i] = heap[i],heap[0]
sift(heap,0,i-1)
return heap
def heap_sort(li):
n = len(li)
for i in range((n-2)//2,-1,-1):#i表示建堆时调整部分根的下标
sift(li,i,n-1) #设high指最后一层
#建堆完毕
for i in range(n-1,-1,-1):#i指向当前堆的最后一个节点的位置
li[0],li[i] = li[i],li[0]
sift(li,0,i-1)#i-1是新的high
import random
li = list(range(1000))
random.shuffle(li)
print(li)
print(topk(li,100))
归并排序
假设现在的列表分成两段有序，如何将其合成一个有序列表，这样的操作称为一次归并。
#局部有序的排序
def merge(li,low,mid,high):#同向双指针
i = low
j = mid+1
l_tmp = []
while i <= mid and j <= high:#需要两边都有数
if li[i]<li[j]:
l_tmp.append(li[i])
i += 1
else:
l_tmp.append(li[j])
j += 1
#执行完while后，肯定有一部分没有数
while i <= mid :
l_tmp.append(li[i])
i += 1
while j <= high:
l_tmp.append(li[j])
j+= 1
li[low:high+1] = l_tmp
li = [2,4,5,7,4,6,7,8]
merge(li,0,3,7)
#print(li)
def merge_sort(li,low,high):
mid = (low+high)//2
if low < high:#至少有两个元素
merge_sort(li,low,mid)
merge_sort(li,mid+1,high)
merge(li,low,mid,high)
merge_sort(li,0,7)
print(li)
希尔排序
一种分组插入排序。
首先取一个整数d1=n/2,将元素分为d组，每组相邻元素之间距离为d1,在各组内进行直接插入排序；
取第二个整数d2=d1/2,重复上述分组排序过程，直到di=1,即所有元素在同一组内进行直接插入排序。
希尔排序每趟并不是使某些元素有序，而是使整体数据越来越接近有序，最后一趟排序才能使数据有序。
def insert_sort_gap(li,gap):
for i in range(gap,len(li)):
tmp = li[i]
j = i-gap
while j>=0 and li[j]>tmp:#比摸到的牌大的数往后移,j相当于一个小指针
li[j+gap] = li[j]
j -= gap
li[j+gap] = tmp
def shell_sort(li):
d = len(li)//2
while d >= 1:
insert_sort_gap(li,d)
d//=2
计数排序
对列表进行排序，已知列表中的数范围都在0到100之间。
#不是比较方法
def count_sort(li,max_count=100):
count = [0 for _ in range(max_count+1)]
for val in li:
count[val] += 1
li.clear()
for ind, val in enumerate(count):#得到每一个数字出现的频数
for i in range(val):
li.append(ind)
import random
li = [random.randint(0,100) for _ in range(100)]
print(li)
count_sort(li,max_count=100)
print(li)
# li = [1,2,3,6,3,4,2,1]
# count_sort(li,max_count=100)
# print(li)
桶排序
在计数排序中，如果元素的范围比较大，可以使用桶排序。
桶排序：首先将元素分在不同的桶中，再对每个桶中的元素排序。
def bucket_sort(li,n = 100,max_num = 10000):
bucket = [[] for _ in range(n)]#创建一个二维列表
for val in li:
i = min(val//(max_num//n),n-1)#放到第几号桶中，对于最后一个数，选择放在最后一个桶中
bucket[i].append(val)
#排序 类似于冒泡排序 从后往前逐一地与前面地数进行比较
for j in range(len(bucket[i])-1,0,-1):
if bucket[i][j]<bucket[i][j-1]:
bucket[i][j],bucket[i][j-1] = bucket[i][j-1],bucket[i][j]
else:
break
sorted_li = []
for buc in bucket:
sorted_li.extend(buc)## extend:追加列表，列表被拆分为一个一个元素
return sorted_li
import random
li = [random.randint(0,10000) for i in range(100)]
print(li)
#bucket_sort(li)
print(bucket_sort(li))
基数排序
多关键字排序：如加入现在有一个员工表，要求先按照薪资排序，年龄相同的员工按照年龄排序。
#类似于多关键词排序
#多次装桶，按照位数从小到大装桶，最后输出，没有桶内排序的过程
#个位进桶，十位进桶，百位进桶等
def radix_sort(li):
max_num = max(li)
it = 0
while 10**it <= max_num:
buckets = [[] for _ in range(10)]
for val in li :
digit = (val // 10**it)%10
buckets[digit].append(val)
li.clear()
for buc in buckets:
li.extend(buc)
it += 1
li = [234,678,945,34,65,78,231,765,987]
radix_sort(li)
print(li)