本文基于王道的数据结构考研复习指导，仅作为本人的学习笔记，如有误欢迎指正
插入排序
直接插入排序
整个例表[0...i-1, i, i+1...n]，i前面的部分维持有序，从i开始向后遍历无序的部分，不断往前面有序的部分插入，插入流程是
- i与i-1（i前面的元素，即有序列表中最后一个，即最大值）比较
- 如果i大于i-1则说明i比0~i-1都大，故将i插入到有序部分的最后（即保持当前位置不变）
- 如果i比i-1小，则从i-1开始向前寻找合适的位置，一边比较，一边挪动，直到找到合适的位置，再将i对应的值放到该位置
不断地把i位置的元素插入到i前面的有序部分中，直到最后一个插入完成即有序
def insert_sort(A: List[int]):
""" 插入排序 稳定 O(n^2) """
tmp = 0
for i in range(1, len(A)): # i从第二个位置开始
if A[i] < A[i-1]: # 与有序部分最大值比较判断是否需要挪动
tmp = A[i] # 暂存当前值
j = i-1
while(A[j] > tmp and j >= 0): # 向后挪动，将插入位置挪出来
A[j+1] = A[j]
j -= 1
A[j+1] = tmp # 将当前值放入插入位置
空间效率：仅使用了常数个辅助单元，因此空间复杂度为O(1)
时间效率：在排序时向有序子表中插入当前元素共进行了n-1趟，每趟操作都在进行比较和移动，而比较次数和移动次数取决于待排表的初始状态
- 最好情况：初始表基本有序，每趟都只需要比较一次而不用移动元素，时间复杂度为O(n)
- 最坏的情况：初始表逆序，总比较次数$\sum_{i=2}^n{i}$，总移动次数$\sum_{i=2}^n{i+1}$
- 平均情况：初始表状态随机，取最坏和最好的平均值，总比较和总移动次数均约为O($\frac{n_2}{4}$)
稳定性：由于每次插入前总是先比较再移动，所以不会出现相同元素位置发生变化的情况，故直接插入排序是一种稳定的排序方法
适用性：适用于顺序存储和链式存储的线性表。为链式时，可以从前往后的查找元素位置
注意：大部分排序算法都仅适用于顺序存储的线性表
折半插入排序
同样的道理，依次遍历后面无序的部分往前面有序的部分插入，只是将从有序部分中查找插入位置的过程改成二分查找，找到正确的插入位置后再依次挪动，把插入位置挪出来，将值放入
def insert_sort_binary(A: List[int]):
"""折半插入排序 稳定 O(n^2)"""
for i in range(1, len(A)):
tmp = A[i] # 暂存当前值
low, high = 0, i-1
while(low <= high): # 二分查找
mid = int((low+high)/2)
if A[mid] < tmp:
low = mid+1
else:
high = mid - 1
j = i-1
while(j > high): # 向后挪值，将插入位置挪出来
A[j+1] = A[j]
j -= 1
A[high+1] = tmp # 总是在high的下一个位置插入
时间效率：相比直接插入排序只是减少了比较次数，约为O($n\log_2{n}$)，且与表的初始状态无关，仅取决于表中元素数量n。而元素移动次数不变，依赖于待排表的初始状态。因此时间复杂度仍为O($n^2$)
稳定性：折半插入排序是一种稳定的排序方法
适用性：适用于线性表为顺序存储的情况，对于数据量不是很大的排序表，折半插入排序往往具有较好的性能
希尔排序
希尔排序也称缩小增量排序
设置一个步长，每次从第一个元素开始，每隔一个步长取一个元素，将这些间隔步长的一组元素使用插入排序进行排序，然后逐渐缩短步长，直至步长为1。
一边缩短步长，一边对使用当前步长划分的小组进行插入排序。每一次根据步长的排序都会使当前列表逐渐有序。列表逐渐有序，也就逐渐减小了后面几趟排序时的工作量。最后一趟步长为1，也就意味着对当前整个列表进行插入排序，但是得益于前面几趟的排序使得整个列表基本有序，那么当前的排序工作量就被减少了很多。经过最后一趟排序，整个列表就有序了
整个过程就体现了它的名字：缩小增量排序
def shell_sort(A: List[int]):
"""希尔排序 不稳定 O(n^1.3)~O(n^2)"""
n = len(A)
dk = int(n/2) # 初始步长
while(dk >= 1): # 结束出口
for i in range(dk, n, dk): # 从当前小组的第二个开始
if A[i] < A[i-dk]: # 与小组内前一个比较
tmp = A[i]
j = i-dk
while(A[j] > tmp and j >= 0): # 比较、挪动
A[j+dk] = A[j]
j -= dk
A[j+dk] = tmp
dk = int(dk/2) # 不断地减小步长
空间效率：仅使用了常数个辅助单元，空间复杂度为O(1)
时间效率：依赖于增量序列的函数，涉及数学上尚未解决的难题，当n在某个特定范围时时间复杂度约为O($n^{1.3}$)。最坏情况为O($n^2$)
稳定性：当相同关键字记录被划分到不同子表时，可能会改变原有相对次序，故希尔排序是一种不稳定的排序方法
适用性：希尔排序仅适用于线性表为顺序存储的情况
交换排序
冒泡排序
从前往后（或从后往前）两两比较相邻元素的值，若为逆序（A[i]>A[i+1]）则交换他们，直到序列比较完。这一过程成为冒泡，第一次从A[0]到A[n-1]，最大值将被冒泡到最后一个位置即A[n-1]；第二次从A[0]到A[n-2]，次大值将被冒泡到A[n-2]……每一趟冒泡都将一个元素放到其最终的位置。最多n-1趟冒泡就能把所有元素排好序
def bubble_sort(A: List[int], n:int):
"""冒泡排序 稳定 O(n^2)"""
tmp = n-1 # 需要n-1趟冒泡,tmp也为最后一个元素的下标
while(n > 0):
flag = False # 表示本趟冒泡是否发生值交换的标志
for i in range(0, tmp): # 一趟冒泡排序，从0到tmp-1
if A[i] > A[i+1]: # 若为逆序则交换
A[i], A[i+1] = A[i+1], A[i]
flag = True
if not flag:
return # 本趟没有发生交换，则说明序列已经有序，无需再调整
tmp -= 1
空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1)
时间效率：
- 最好情况：原始序列初始有序，第一趟冒泡后flag为False，即结束排序，共比较了n-1次，移动次数为0，故时间复杂度为O(n)
- 最坏情况：原始序列逆序，需要n-1趟排序，第i趟要进行i-1次比较，而每次比较后都必须移动元素3次来交换元素位置（针对原书中的C语言版本
tmp=a;a=b;b=tmp）故共比较了$\sum_{i=1}^{n-1}{(n-1)}=\frac{n(n-1)}{2}$，移动次数$\sum_{i=1}^{n-1}3(n-i)=\frac{3n(n-1)}{2}$。从而最坏情况下时间复杂度为O($n^2$) - 平均时间复杂度：O($n^2$)
稳定性：从前往后，先比较再移动，相邻两元素若相等则不会发生交换，故稳定。
注：冒泡排序不同于插入排序，对于冒泡排序，每一趟排序后都有一个元素被放置到最终的位置上，也就是说全局有序。
快速排序
选定一个枢轴，将小于它的值都交换到它前面，将大于它的值都交换到它的后面，然后对前后两个部分继续递归划分。一般选列表中的第一个作为枢轴，对整个列表进行划分。设置两个标志low和high，low从第一个元素开始，high从最后一个元素开始。
设有一个列表L
- 首先将一个元素赋值给枢轴pivot
- 开始划分
- 将high所指元素与pivot比较，如果L[high]>=pivot，则将high前移指向前一个元素，从后往前直到找到第一个小于pivot的值，将这个值覆盖到L[low]
- low从第一个往后走，直到找到第一个大于pivot的值，将这个值覆盖到L[high]
- 上述1、2两部交替执行，直到low=high，此时这个位置就是pivot的最终位置，将pivot放置到该位置
- 经过上面一趟划分之后，pivot前面的元素都小于它，后面的元素都大于它。pivot将列表L划分为前面小于它的子表，和后面大于它的子表。然后再基于分治的思想对前后两个子表进行划分
def quick_sort(A: List[int], low: int, high: int):
"""快排 不稳定"""
def partition(L: List[int], low: int, high: int) -> int:
"""划分函数"""
pivot = L[low] # 将当前表中第一个元素作为枢轴,对表进行划分
while(low < high): # 循环跳出条件low=high
# 操作1、2交替进行直到low=high，此位置即为pivot的最终位置
# 1.high从后往前，当high的值比枢轴值大时将其放到low对应的位置
while(low < high and L[high] >= pivot):
high -= 1
L[low] = L[high]
# 2.low从前往后前，当low对应的值大于大于枢轴值时将其放到high的位置
while(low < high and L[low] <= pivot):
low += 1
L[high] = L[low]
L[low] = pivot # 此时low=high,将枢轴放置该位置
return low # 返回枢轴的最终位置
if low < high: # 当传入的low=high时不再需要划分
pivotpos = partition(A, low, high) # 根据上一趟枢轴的位置划分子表
quick_sort(A, low, pivotpos-1) # 依次递归排序两个子表
quick_sort(A, pivotpos+1, high)
选择排序
简单选择排序
“设排序表为L[1…n]，第i趟排序即从L[i..n]中选择关键字最小的元素与L[i]交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可以使得整个排序表有序”，通俗的说就是从前往后不断地把最小的值换到前面去。
def select_sort(A: List[int], n:int):
"""选择排序 不稳定"""
for i in range(0, n-1): # 一共进行n-1趟排序
min = i # 记录最小值位置
for j in range(i+1, n): # 在A[i...n-1]中选择最小的元素
if A[j] < A[min]:
min = j # 更新最小元素位置
if min != i:
A[i], A[min] = A[min], A[i] # 将最小值替换到前面的位置
空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1)
时间效率：简单选择排序移动次数较少，最多不会超过3(n-1)次对应逆序，最少0次对应排序表初始有序。比较次数与初始状态无关，始终是$\frac{n(n-1)}{2}$次，因此时间复杂度始终是O($n^2$)
稳定性：在第i趟找到最小元素后，和第i个元素交换，可能导致第i个元素与其含有相同关键字元素的相对位置发生改变。比如{2，2，1}经一趟排序后是{1，2，2}，显然2和2的相对位置发生了变化。因此，简单选择排序是一种不稳定的排序方法。
比较直接插入、冒泡和简单选择排序
直接插入排序：从后往前，从无序部分中取值往前面有序部分中插入，稳定
冒泡排序：从后往前，一边比较一遍交换挪动位置，每趟都会确定一个元素的最终位置，稳定
简单选择排序：从当前元素往后找出最小值的位置，然后将最小值和当前位置的元素交换，每趟都会确定一个元素的最终位置，但是不稳定，比如[2,2,1]交换排序后就是[1,2,2]，第一个2和第二个2相对顺序发生了变化
堆排序
堆的定义如下：
-
L[i]>L[2i]且L[i]>L[2i+1] 或
-
L[i]<L[2i]且L[i]<L[2i+1] (1≤i<≤⌊n/2⌋)
可以将一个一维数组视为一颗完全二叉树，满足上述条件一的为大根堆，注意：节点序号是从1开始的
当前节点序号为n，其左孩子序号为2*n，其右孩子节点为2*n+1
借助最大堆或最小堆进行排序（注意：最大堆、最小堆与二叉排序数不同！最大堆只是根节点比子节点大，但是左右子节点之间并没有固定的大小关系；二叉排序树中，左儿子最小，根节点居中，右儿子最大，所以二叉排序树的中序遍历得到的序列即是有序的）。构建出初始最大堆后，输出堆顶元素，然后“删除”，将最后一个叶节点移到堆顶位置，重新调堆，输出堆顶元素……重复上述过程
def heap_sort(A: List[int], length: int):
"""堆排序 不稳定 O(nlog2n)"""
def bulid_max_heap(L: List[int], length: int):
"""构建最大堆"""
i = int(length/2) # 最后一个父节点，根据完全二叉树的性质
while(i > 0): # 从i= ⌊n/2⌋~1，反复调堆，注意节点下标是从1开始的
adjust_heap(L, i, length)
i -= 1
def adjust_heap(L: List[int], k: int, length: int):
# 调整以元素K为根节点的子树
# 第一个节点要预留（即下标为0的节点）
L[0] = L[k] # 使用L[0]暂存子树的根节点
i = 2*k # 第一个子节点
while i <= length:
if i < length and L[i] < L[i+1]: # 沿key较大的子节点向下筛选
i += 1 # 取key较大的子节点的下标
if L[0] > L[i]: # 根节点大于最大的子节点，不需要再调整
break
else:
L[k] = L[i] # 将L[i]调整到双亲节点上
k = i # 修改K值，继续向下筛选，K值即为当前的双亲节点
i *= 2 # 继续
L[k] = L[0] # 被筛选节点的值放入最终位置
bulid_max_heap(A, length) # 创建初始堆
n = length
while n >= 1: # 注意下标为0的节点“不存储数据”
A[1], A[n] = A[i], A[n] # 交换堆顶和堆低元素，相当于把最大值移到最后的位置
n -= 1 # "缩短长度"，调整堆的大小，把剩余n-1个元素整理成堆
adjust_heap(A, 1, n)
归并排序
“归并就是将前后两个有序表归并成一个有序表。设两段有序表A[low…mid], A[mid+1…high]存放在同一顺序表中的相邻位置，先将他们复制到数组B中。每次从对应B中的两个段中取出一个记录进行关键字比较，将较小者放入A中，当数组B中有一段的下标超出其对应的表长（即该段的所有值都已复制到A中）时，将另一段中剩余的部分直接复制到A中。”
通俗的说：归并就是将两个有序表合成一个，将原表先拷贝一份，然后从中间分为左右两个子表，依次比较左右两个表中的值，并将较小值插入原表，若最后左右子表中还有一个有剩余的，则将剩余的元素直接复制到原表中
递归形式的2路归并排序是基于分值的，先一直向下划分 mid = ( low + high ) / 2，直到low=high-1（递归出口），即low与high相邻，此实左右子表都只有一个元素，即左右子表此时都是有序的，然后就可以开始合并了，一直向上合并直到最上面一层合并完成
def merge_sort(A: List[int], low: int, high: int):
"""归并排序 二路归并 稳定 O(n*log2n)"""
def merge(A: List[int], low: int, mid: int, high: int):
# 合并左右两段有序的序列A[low..mid]和A[mid+1...high]
B = A.copy() # 把A拷贝一份，然后直接在A上调整
i = low
j = mid+1
k = i
while i <= mid and j <= high: # 比较、挪动、将较小值放回A中
if B[i] < B[j]: # 比较B中左右两段中的元素
A[k] = B[i]
i += 1 # 将较小值放入A中
else:
A[k] = B[j]
j += 1
k += 1
# 下面两个while只有一个会执行
while i <= mid: # 左侧序列未检测完、复制
A[k] = B[i]
k += 1
i += 1
while j <= high: # 右侧序列未检测完、复制
A[k] = B[j]
k += 1
j += 1
if low < high:
# 递归条件，只有当low=high-1时，即low、high相邻时才停止递归
# 此时，左右两段各有一个值，即左右两段都有序，则开始执行merge合并有序段
# 然后向上回退，一边回退一边merge
# 递归形式的二路归并
mid = int((low+high)/2) # 从中间划分两个子序列
merge_sort(A, low, mid) # 对左侧子序列进行递归排序
merge_sort(A, mid+1, high) # 对右侧子序列进行递归排序
merge(A, low, mid, high) # 归并
各种排序算法的比较
| 算法 | O(最好情况) | O(平均情况) | O(最坏情况) | 空间复杂度 | 是否稳定 |
|---|---|---|---|---|---|
| 直接插入排序 | O(n) | O($n^2$) | O($n^2$) | O(1) | ✅ |
| 冒泡排序 | O(n) | O($n^2$) | O($n^2$) | O(1) | ✅ |
| 简单选择排序 | O($n^2$) | O($n^2$) | O($n^2$) | O(1) | ❌ |
| 希尔排序 | ❌ | ||||
| 快速排序 | O($nlog_2n$) | O($nlog_2n$) | O($n^2$) | O($log_2n$) | ❌ |
| 堆排序 | O($nlog_2n$) | O($nlog_2n$) | O($nlog_2n$) | O(1) | ❌ |
| 2路归并排序 | O($nlog_2n$) | O($nlog_2n$) | O($nlog_2n$) | O(n) | ✅ |