[算法导论]非比较排序及数据结构

并非基于比较策略的排序,可以突破比较排序Ω(NlogN)的限制,打倒O(N)的水平

计数排序 o(n+k) 稳定排序

create c[1...k]=0

create b[1...n]

for i= 1 to n

　　do c[i]++

for j= 2 to k

　　do c[j]=c[j]+c[j-1]

for r=n to 1

　　do b[c[a[r]]]=a[r]

　　　　c[a[r]]--

基数排序 稳定,局部使用插入排序

从低位开始排

l

桶排序

中位数与顺序统计学

最大与最小值 各需要O(n)

同时找到,O(3/2n), 比较时两个两个取

寻找第k顺序位数字,O(n),非比较策略

find_select(a,p,r,k)

q=PARTITION(a,p,r)

if q==k return a[q]

if q>k do find_select(a,p,q,k)

else do find_select(a,q,r,k-q)

数据结构