排序介绍

列表排序：将无序列表变成有序列表（升序或降序）

内置排序函数：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 = Trueif 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_newli = [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 = ifor j in range(i+1,len(li)):if li[j] < li[min_loc]:min_loc = jli[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-1while j>=0 and li[j]>tmp:#比摸到的牌大的数往后移,j相当于一个小指针li[j+1] = li[j]j -= 1li[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 += 1li[right] = li[left]#把左边的值写到右边的空位上li[left] = tmp#将tmp归位return leftdef 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+1else: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+1else: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 heapdef 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是新的highimport random
li = list(range(1000))
random.shuffle(li)
print(li)
print(topk(li,100))

归并排序

假设现在的列表分成两段有序，如何将其合成一个有序列表，这样的操作称为一次归并。

#局部有序的排序
def merge(li,low,mid,high):#同向双指针i = lowj = mid+1l_tmp = []while i <= mid and j <= high:#需要两边都有数if li[i]<li[j]:l_tmp.append(li[i])i += 1else:l_tmp.append(li[j])j += 1#执行完while后，肯定有一部分没有数while i <= mid :l_tmp.append(li[i])i += 1while j <= high:l_tmp.append(li[j])j+= 1li[low:high+1] = l_tmpli = [2,4,5,7,4,6,7,8]
merge(li,0,3,7)
#print(li)def merge_sort(li,low,high):mid = (low+high)//2if 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-gapwhile j>=0 and li[j]>tmp:#比摸到的牌大的数往后移,j相当于一个小指针li[j+gap] = li[j]j -= gapli[j+gap] = tmpdef shell_sort(li):d = len(li)//2while 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] += 1li.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:breaksorted_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 = 0while 10**it <= max_num:buckets = [[] for _ in range(10)]for val in li :digit = (val // 10**it)%10buckets[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)