排序算法
冒泡排序 O(n2) 内部排序,稳定排序
for i = n to 2
for j = 1 to i-1
if a[j]>a[j+1]
do exchange a[j] and a[j+1]
end
end
插入排序 O(N2) 内部排序 虽然复杂度较高,但实际应用中效果较好,小规模适合,最优O(N) 稳定排序
for i = 2 to n
d=a[i]
j = i-1
while j>=1 and a[j]>a[j+1]
do a[j+1]=a[j];
a[j]=d;
end
归并排序 O(NlogN) 外部排序,但复杂度低,最后算法的逼近 稳定排序
merge(a,p,q,r)
{
i=q-p+2
j=r-q+1
create b[1...i-1]=a[p...q],c[1...j-1]=a[q+1...r]
b[i]=+∞ c[j]=+∞
m=n=1
for s=p to r
if b[m]<c[n]
do a[s]=b[m]
m++ s++
else do a[s]=c[n]
n++ s++
end
end
}
merge_sort(a,x,y)
{
merge_sort(a,x,(x+y)/2)
merge_sort(a,(x+y)/2+1,y)
merge(a,x,(x+y)/2,y)
}
堆排序 O(NlogN) 内部排序,最优渐进 不稳定排序
max_heap(a,r)
{
i=r*2
j=r*2+1
large=r
if a[i]>a[large] do large=i
if a[j]>a[large] do large=j
if large!=r do exchange a[r] and a[large]
if large<heap_size/2 do max_heap(a,large)
}
build_max_heap(a,n)
{
for i= n/2 to 1 do max_heap(a,i)
}
heap_sort(a,n)
{
heap_size=n
build_max_heap(a,n)
while heap_size>=1
do exchange a[1] and a[heap_size]
heap_size--
max_heap(a,1);
}
快速排序 期望复杂度为O(NlogN) 最坏情况为O(N2),但系数因子小,实用中比其他都要好,内部排序 不稳定排序
p=partition(a,r)
{
d=a[r]
i=0;
for j=1 to r-1
if a[j]<a[r]
do i++
exchange a[i] and a[j]
end
p=i+1
exchange a[r] and a[p]
}
quick_sort(a,n)
{
p=partition(a,n)
quick_sort(a,p-1)
quick_sort(a,p+1)
}
排序稳定性:相同关键字的元素相对位置是否会交换.56529,第一个5和2交换则是不稳定的
主定理:
T(n)=aT(n/b)+f(nc)
1. log(b)a<c 则O(nc)
2. log(b)a=c 则O(nclogn)
3. log(b)a>c 则O(n(log(b)a))