Posted on 2008-03-30 21:33
迎风十八刀 阅读(329)
评论(0) 编辑 收藏 所属分类:
算法
简单插入排序:
Insertion-Sort(A):
1.for j = 2 to length[A]
2. do key=A[j]
3. //insert A[j] into the sorted sequence A[1..j-1]
4. i = j-1
5. while i>0 and A[i]>key
6. do A[i+1] = A[i]
7. i = i-1
8. A[i+1] = key
T(n)=O(n2) ,稳定，空间为O(1)
合并排序:
Meger-Sort(A,p,r):
1. if p < r
2. then q = floor((p+r)/2)
3. Meger - Sort(A,p,r)
4. Meger - Sort(A,q+1,r)
5. Meger(A,p,q,r)
T(n)=O(nlgn), 稳定，空间O(n)