?涉及的排序算法
| 排序LowB 三人组 O(n^2) | 排序NB三人组 O(nlogn) | 其他排序 |
|---|
| 冒泡排序 | 快速排序 | 计数排序 | | 选择排序 | 堆排序 | 桶排序 | | 插入排序 | 归并排序 | 基数排序 | | | 希尔排序 |
一、冒泡排序（Bubble Sort）
思想：比较列表相邻的两个数，如果前面的数比后面的数大，就交换这两个数，每走一趟，就会将无序部分的最大值放到无序部分的末尾。理论需要比较n-1趟。优化：如果有一趟没有交换，说明已经全部有序，可以停止。
| 9 | 8 | 7 | 1 | 2 | 3 | 4 | 5 |
|---|
| 8 | 7 | 1 | 2 | 3 | 4 | 5 | 9 | | 7 | 1 | 2 | 3 | 4 | 5 | 8 | 9 | | 1 | 2 | 3 | 4 | 5 | 7 | 8 | 9 |
def bubble_sort(li):
for i in range(len(li)-1): # 最多需要比较 n-1 趟，n=len(li)
exchange = False # 记录该趟是否有交换
for j in range(len(li)-1-i): # 列表末尾是有序区
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
exchange = True
if not exchange: # 如果没有交换，说明已经全部有序
return
?二、选择排序（Select Sort）
思想：遍历一遍列表选择最小值放在无序区的头部，不断重复。普通：创建新列表依次存储每一次的最小值（新列表就是有序区），使用min()和remove()。优化：就地排序，找到最小值与无序区头部元素交换。
# 创建新列表存储有序区
def select_sort(li):
new_li = []
for _ in range(len(li)):
min_val = min(li)
new_li.append(min_val)
li.remove(min_val)
return new_li
# 就地排序
def select_sort(li):
n = len(li)
for i in range(n):
min_loc = i # min_loc 表示当前无序区最小值所在索引
for j in range(i+1, n):
if li[j] < li[min_loc]:
min_loc = j
li[min_loc], li[i] = li[i], li[min_loc]
return li
三、插入排序（Insert Sort）
思想：想象打牌，初始手里（有序区）有一张牌（第一张），每次从牌堆中（无序区）摸出一张牌插到正确位置。
def insert_sort(li):
for i in range(1, len(li)): # 第一张牌直接放在有序区，所以从1开始；i开始当前从无序区中摸出的牌
j = i - 1 # j 是有序区的右边界
tmp = li[i]
# 找出摸出的牌 tmp 应该插入有序区的位置，从有序区右边开始比较，如果比tmp大，就不断右移
while j >= 0 and tmp < li[j]: # j=-1时表明已经找到有序区最左边了
li[j+1] = li[j]
j -= 1
li[j] = tmp
return li
四、快速排序（Quick Sort）
思想：取一个元素（初始一般取第一个）p，将p归位，即将列表中比p小的放在p左边，比p大的放p的右边。这样列表就被p分成两部分，然后分别再堆p的左右两边重复以上操作。
| 5 | 8 | 7 | 1 | 3 | 2 | 4 | 9 |
|---|
| 4 | 2 | 3 | 1 | 5 | 7 | 8 | 9 | | 1 | 2 | 3 | 4 | 5 | 7 | 8 | 9 | | 1 | 2 | 3 | 4 | 5 | 7 | 8 | 9 |
# 归位函数，将p放在其正确的位置上，p左边元素都比p小，右边元素都比p大
def partition(li, left, right): # left，right分别是li的左右边界
p = li[left] # 当前left位置的数已经保存在p中，可将left位置视为空位
while left < right:
# 从右边找到比p小的值，并放到left位置上
while left < right and li[right] > p：
right -= 1
li[left] = li[right]
# 从左边找到比p大的值，并放到right位置上
while left < right and li[left] < p:
left += 1
li[right] = li[left]
li[left] = p # p归位，此时left=right，使用left和right都可
return left # p将li分为两部分，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)
五、堆排序（Heap Sort）
思想：堆是一种特殊的完全二叉树（完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的叶节点都集中在该层最左边的若干位置的二叉树），大根堆满足任一节点都比孩子节点大，小根堆满足任一节点都比其他孩子节点小。堆的向下调整性质：假设节点的左右子树都是堆，但是自身不是堆，当根节点的左右子树都是堆时，可以通过一次向下的调整来将其变成一个堆。
应用：Top K问题
# 大根堆的一次向下调整，将顶点元素放到合适位置，中间需要不断将较大的元素往上调
def sift(li, low, high): # low表示当前堆的根节点，即新加入元素暂时所在位置，high表示堆的最后一个元素的位置
i = low
tmp = li[low]
j = 2 * i + 1 # j节点是i节点的左孩子，j用意是用来指向i的较大孩子
while j <= high: # 只要j位置还有数
# 首先找出i节点的左右孩子节点中较大的孩子，并赋给j
if j + 1 <= high and li[j+1] > li[j]: # 右孩子存在且比左孩子大
j += 1
# 如果i的较大孩子大于i，就将大孩子（即j）放到i位置，并更新i
if li[j] > tmp:
li[i] = li[j]
i = j
j = 2 * i + 1
# tmp 比i的孩子都大（此时i可能是更新后的，所以i不一定是low了），则找到tmp所在位置
else:
li[i] = tmp
break
# 节点i的根节点1为(i-1)//2,所以节点n-1的根节点为(n-2)//2
def heap_sort(li):
n = len(li) # 最后一个节点索引为n-1
# 第一步，建堆，从下往上
for i in range((n-2)//2, -1, -1): # 从最后节点的根节点开始
# i表示建堆时调整部分的根节点的下标
sift(li, i, n-1)
# 建堆已完成，就地排序
# 将堆顶元素依次存在最后一个元素中，最后一个元素放到堆顶进行一次向下调整，最终列表就是升序的
for i in range(n-1, -1, -1):
# i指向当前堆的最后一个元素
li[i], li[0] = li[0], li[i]
sift(li, 0, i-1)
使用 python 堆排序的内置模块 heapq
import heapq # 默认小根堆，建立大根堆就需要对元素取反
heap = [] # 堆
for i in range(len(li)):
heapq.heappush(heap, li[i])) # 将li元素依次入堆，小根堆
for i in range(len(li)):
li[i] = heapq.heappop(heap) # 依次弹出堆顶元素（堆中最小元素）更新li
# 堆中元素可以是元组，默认对第一个元素排序，例如 heapq.heappush(heap, (a,b,c))
六、归并排序（Merge Sort）
思想：将两段有序的列表合并成一个有序的列表称为一次归并，使用分治法，将列表不断对半切分，知道每一段只有一个元素，就从下往上不断进行归并。
def merge_sort(li, low, high):
if low >= high:
return
mid = (low + high)//2 # 左数组的右边界
merge_sort(li, low, mid)
merge_sort(li, mid+1, high)
tmp = [] # 暂存排序数组
# 此时 li[low,mid+1] 和 li[mid+1,high+1] 已经是有序数组了
left, right = low, mid+1
while left <= mid and right <= high:
if li[left] <= li[right]:
tmp.append(li[left])
left += 1
else:
tmp.append(li[right])
right += 1
while left <= mid:
tmp.append(li[left])
left += 1
while right <= high:
tmp.append(li[right])
right += 1
li[low:high] = tmp
七、计数排序（Count Sort)
思想：已知列表的元素分为，统计每个元素的个数，依次排开即可得到排好序的列表，时间复杂度O(n)。可用于年龄排序，优点是快，缺失是当元素分为大时空间复杂度会很大，即O(元素范围)
# 假设已知元素范围是[0,100]
def count_sort(li, max_count = 100):
# 生成长度为 max_count+1,元素全为0的列表count存放待排序列表元素的计数
count = [0 for _ in range(max_count+1)]
for val in li:
count[val] += 1
li.clear()
for val, num in enumenrate(count):
for i in range(num)
八、桶排序（Bucket Sort）
思想：计数排序的改进。当元素范围很大时，例如上亿，计数排序空间消耗太大。推排序是将元素分在不同的桶中，例如元素范围[1,1000]，分10个桶，分别存储范围为[1,10],[11,20]...的元素。分桶后用别的方法对桶中的元素进行排序，也可以在元素入桶时就排序。桶排序的时间复杂度取决于数据的分布，也就是需要对不同数据排序时采取不同的分桶策略。
时间复杂度分析：n个数，分m个桶，假设数据平均分布，则每个桶 k = n/m 个元素，桶中采取快速排序，时间复杂度 O(klogk) , 桶排序时间复杂度：
m*O(klogk) = m*O(n/m*log(n/m)) = O(n*log(n/m))
当桶的个数m接近于n时，log(n/m)是一个较小的数，所以桶排序时间复杂度近似 O(n）。但要求数据分布较均匀，如果说数据不均匀，全分到一个桶中，就为了一个快排。
?
# 对范围[0,1000]元素，分100个桶,第一个桶元素范围[0,100),这样最后多出一个1000，可以放在最后一个桶中
def bucket_sort(li, n=100, max_num=1000):
buckets = [[] for _ in range(n)] # 创建 n 个桶
space = max_num//100
for val in li:
i = min(val//space, n-1) # i表示痛的编号，如果元素过界就放在最后一个桶中，例如1000
buckets[i].append(val) # 元素入桶
# 入桶就保持桶内的元素的顺序，可以使用冒泡排序/插入排序
for j in range(len(buckets[i])-1, 0, -1):
if buckets[i][j] < buckkets[i][j-1]: # 桶中升序
buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j]
else:
break # 只要没有进行交换就表明已经有序了
sorted_li = [] # 存放存放排好序的列表
for buc in buckets:
sorted_li.extend(buc)
return sorted_li
九、基数排序（Radix Sort）
思想：类似多关键字层次排序，例如先个位数分桶回位，再十位分桶回位，百位分桶回位。时间复杂度O(d(n+k))=O(n), d为最大位数，k为每一位数的范围。适用于位数不多，每一位范围不大的情况（对于数字来说都是0-9）。
?
def radit_sort(li):
for i in range(len(str(max(li)))): # 通过数组中的最大数来判断位数数量
# 桶的个数就是每一位数的范围，都是0-9, 10个桶
buckets = [[] for _ in range(10)]
for num in li:
# 求对应数位的数字，例如1678，百位数字 6 = 1678//100%10 = 1678//(10**2)%10 = 1678//(10**i)%10
buckets[num//(10**i)%10].append(num)
# 写回
li = [num for buc in buckets for num in buc]
十、希尔排序（Shell Sort）
思想：希尔排序是一种分组插入排序算法。时间复杂度于gap有关
1. 取整数 d1=n//2，将序列交叉分成d1个组（第1个元素于第d1+1个元素为一组，2和d1+2为一组），每组相邻元素之间的距离为d1，在各组内进行直接插入排序。
2. 取第2个整数 d2=d1//2,，重复上述分组排序，直到 di=1，即所有元素在同一组内直接进行插入排序。
3. 希尔排序每趟并不是某些元素有序，而是使整体数据越来越接近有序，最后一趟使得所有数据有序。
| 7 | 1 | 5 | 9 | 4 | 2 | 3 | 8 | 6 | | n=9,? d1 = 9//2=4, 分成4组， 7 4 6一组， 1 2一组， 5 3 一组， 9 8一组，插入排序后 | | 4 | 1 | 3 | 8 | 6 | 2 | 5 | 9 | 7 | | d2 = 4//2 = 2, 分成2组，4 3 6 5 7 一组， 1 8 2 9 一组，插入排序后 | | 3 | 1 | 4 | 2 | 5 | 8 | 6 | 9 | 7 | | d3 = 2//2 = 1, 全部元素为一组，插入排序后 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
?
# 分组插入排序函数，对各组分别进行插入排序
def insert_sort_gap(li, gap): # gap 表示分的组数，即d
for i in range(gap, len(li)): # 插入排序，每组第一个元素作为有序区的元素，所以无序区元素从每组第二个元素开始
tmp = li[i] # 暂存摸到的牌
j = i - gap # j指向当前牌所在组的有序区的右边界
while j >= 0 and li[j] > tmp:
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
?
|