递归-排序
文章目录
主定理
在算法分析中，主定理（英语：master theorem）提供了用渐近符号（大O符号）表示许多由分治法得到的递推关系式的方法
递归式子中三种情况：大部分操作（消耗时间）运行在根节点上，叶节点上或递归树的各行之间。
情形一
如果存在常数 $\epsilon >0$，有
$ f(n)=O\left(n^{\log _{b}(a)-\epsilon }\right) $ (多项式地小于）
那么
$ T(n)=\Theta \left(n^{\log _{b}a}\right) $
情形二
如果存在常数 k ≥ 0，有
$ f(n)=\Theta \left(n^{\log _{b}a}\log ^{k}n\right)$
那么
$T(n)=\Theta \left(n^{\log _{b}a}\log ^{k+1}n\right)$
情形三
如果存在常数$ \epsilon >0$，有
$f(n)=\Omega \left(n^{\log _{b}(a)+\epsilon }\right)$（多项式地大于）
同时存在常数$ c<1$以及充分大的 $n$，满足
$af\left(\frac {n}{b}\right)\leq cf(n)$
那么
$T\left(n\right)=\Theta \left(f\left(n\right)\right)$
归纳(induction)、递归(recursion)及 归简(reduction)
归简法是指将某一问题转换称另一个问题。如将一个未知问题转换称一个已解决问题。
归纳法则用于证明某个语句对于大型对象类是否成立。
递归法则用于函数自我调用时。
排序算法
冒泡排序
在无序区查找最大元素放置最后，循环n次，复杂度$O(n^{2})$，稳定，$O(1)$。1
2
3
4
5def bubble_sort(seq):
for i in range(len(seq)-1,0,-1):
for j in range(i-1,0,-1):
if seq[i]<seq[j]:
seq[j],seq[i]=seq[i],seq[j]
选择排序
$O(n^{2})$，对数组稳定（链表不稳定），$O(1)$。
1
2
3
4
5
6def sel_sort(seq):
for i in range(len(seq)-1,0,-1):
max_j=i
for j in range(i):
if seq[j]>seq[max_j]: max_j=j
seq[i],seq[max_j]=seq[max_j],seq[i]
插入排序
假设前 n-1 个数据已排好序，现在要将 n 插入到合适的位置（将无序区的元素插入到有序区的合适位置）。$O(n^{2})$，稳定，$O(1)$。
1
2
3
4
5
6def ins_sort(seq):
for i in range(1,len(seq)):
j=i
while j>0 and seq[j-1]>seq[j]:
seq[j-1],seq[j]=seq[j],seq[j-1]
j-=1
归并排序
将问题归简为两个相等子问题，依次递归。$O(n\log n)$，空间复杂度 $O(n)+O(\log n)$(从上往下)$O(1)$(从下往上),稳定。
1
2
3
4
5
6
7
8
9
10
11
12
13def mergesort(seq):
mid=len(seq)//2
lft,rgt=seq[:mid],seq[mid:]
if len(lft)>1:lft=mergesort(lft)
if len(rgt)>1:rgt=mergesort(rgt)
res=[]
while lft and rgt:
if lft[-1]>=rgt[-1]:
res.append(lft.pop())
else :
res.append(rgt.pop())
res.reverse()
return (lft or rgt)+ res
计数排序
统计每一个数字出现的次数。 $O(n+m)$，稳定，$O(n+m)$。
1
2
3
4
5
6
7
8from collections import defaultdict
def counting_sort(seq,key=lambda x:x):
B,C=[],defaultdict(list)
for x in seq:
C[key(x)].append(x)
for k in range(min(C),max(C)+1):
B.extend(C[k])
return B
基数排序
对数字的每一位进行排序。$O(k\times n)(平均) O(n^{2})(最坏)$，稳定，$O(n)$。
1
2
3
4
5
6
7
8
9
10import math
def radix_sort(seq,radix=10):
K=int(math.ceil(math.log(max(seq)+1,radix)))
for i in range(1,K+1):
bucket=[[] for i in range(radix)]
for val in seq:
bucket[val%(radix**i)//(radix**(i-1))].append(val)
del seq[:]
for each in bucket:
seq.extend(each)
堆排序
使用堆结构的性质。$O(n\log n)$，不稳定，$O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20def heap_sort(seq):
def sift_down(start,end):
root=start
while True:
child=2*root+1
if child>end:
break
if child+1<=end and seq[child]<seq[child+1]:
child+=1
if seq[root]<seq[child]:
seq[root],seq[child]=seq[child],seq[root]
root=child
else:
break
for start in range((len(seq)-2)//2,-1,-1):
sift_down(start,len(seq)-1)
for end in range(len(seq)-1,0,-1):
seq[0],seq[end]=seq[end],seq[0]
sift_down(0,end-1)
return seq
快速排序
分解为两个子问题，时间代价主要在分解上，$left<right$。$O(n\log n)(平均) O(n^{2})(最坏)$，不稳定，$O(\log n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16def quicksort(seq,left,right):
if left<right:
p=partition(seq,left,right)
quicksort(seq,left,p)
quicksort(seq,p+1,right)
return
def partition(seq,lft,rgt):
pivot=seq[rgt-1]
i=lft-1
for j in range(lft,rgt):
if seq[j]<pivot:
i+=1
seq[i],seq[j]=seq[j],seq[i]
if seq[rgt-1]<seq[i+1]:
seq[i+1],seq[rgt-1]=seq[rgt-1],seq[i+1]
return i+1
希尔排序
插入排序的进化版。 $O(n\log ^{2}n)(平均) O(n^{2})(最坏) $，不稳定，$O(1)$.
1
2
3
4
5
6
7
8
9
10
11
12
13def shell_sort(seq):
n=len(seq)
gap=n//2
while gap>0:
for i in range(gap,n):
temp=seq[i]
j=i
while j>=gap and seq[j-gap]>temp:
seq[j]=seq[j-gap]
j-=gap
seq[j]=temp
gap=gap//2
return seq
桶排序
数据分为几组。组间有序，组内再排序。 $O(n)$，稳定，$O(m)$.
1
2
3
4
5
6
7
8
9def bucket_sort(seq,n=10):
buckets=[[]for i in range(n)]
for i in range(0,len(seq)):
buckets[seq[i]//n].append(seq[i])
for i in range(0,n):
buckets[i]=mergesort(buckets[i])
del seq[:]
for x in buckets:
seq.extend(x)