排序
众说周知,排序是一种很重要的算法,一组数据的有序性对数据的处理有重要的意义。
排序算法也是多种多样的,从 到以及甚至寂寞的 ……
对于冒泡排序,选择排序及其优化,或者说是分治思想,在此不再赘述,这里主要探讨堆排序的思想以及与线段树的关系。
堆排序
堆排序的思想其实挺简单的,其算法描述如下:
1.得到一个数集S
2.从S中选出一个最小的数a
3.把a放入已排序数集G中,并把a从S中删去。
4.重复1,2,3直到S为空。
然后代码大概就这样写
// let q be a minium heap
void heap_sort(int *sorted,int *unsort,int length){
for(int i=1;i<=length;++i) q.push(unsort[i]);
while(!q.empty()){
int now=q.top();
q.pop();
sorted[++sorted[0]]=now;
}
}
线段树
首先,线段树大法好。
之前也写过用线段树写Dijkstra的文章,那么我们为什么不能用它排序呢？
同样的,线段树存储数组的下标,然后把一个数改为最大值意味着它已经被放入数集G中。
int tree[N],leaf;
int ck(int *a,int i,int j){
return a[i]<a[j]?i:j;
}
void build(int *a,int length){
leaf=1;
while(leaf<=n) leaf=leaf<<1;--leaf;
for(register int i=1;i<=n;++i) tree[i+leaf]=i;
for(register int i=leaf;i;--i) tree[i]=ck(a,tree[i<<1],tree[i<<1|1]);
}
void change(int *a,int x,int y){
a[x]=y,x+=leaf,x=x>>1;
while(x) tree[x]=ck(a,tree[x<<1],tree[x<<1|1]),x=x>>1;
}
void _sort(int *sorted,int *unsort,int length){
build(unsort,length);
for(int i=1;i<=n;++i){
const int v=tree[1];
sorted[++sorted[0]]=a[v];
change(v,0x7fffffff);
}
}
虽然它和STL_sort 还是有较大的距离,不过似乎比手写的其它排序还是快很多了。
Summary
这样看来,线段树似乎越来越接近堆的作用了,目前能想到的做法是开能存储(N+M)个元素的线段树来模拟堆(M为询问个数),来模拟堆。
线段树真是个好东西www