非常强悍的堆排序
2011-03-28
如何生成m个随机数?看了编程珠玑的文章,知道了一些,后来又在csdn上发现了其他人设计的,我就拿来说说吧。如果没有头绪,那就按平常来说就是随机生成一个数,然后比较集合中是否存在,不存在放里面,否则再继续生成。按珠玑上所言,那就是 psuedo :
select =m; remaining =n; for i=[0..n] if(bigrand()%remaining)<select set.add(i) select--; remaining--;
代码:
void getknuth(int m,int n) { for (int i=0;i<n;i++) if(bigrand()%(n-i))<m) { cout<<i<<endl; m--; } }
另外一种方式是先从0到n生成按i递增生成n个数先,然后再随机打乱这m个数的位置并选中。
一次循环搞定:
for(int i=0;i<n;i++) a[i]=i; for(int j=0;i<m;j++) { swap(a[j],a[random()%j]); }
还有一种与上述类似,就每个数据初始化为0,随机选中一个位置 如果该位置为零就没有赋值过,就赋值为i:
int a[100]={0}; int i, m; for(i=1; i<=99; ++i) { while(a[m=rand()%100]); a[m] = i; }
该方法效率不高(因为很可能生成重复的位置),该章后面的原理部分很好:
- 正确理解你所遇到的问题
- 提炼抽象问题
- 考虑尽可能多的解法
- 实现一种解决方案
这些建言真的很不错,思考的时间和深度是和解决问题的力度成正比的。
好,说完题外话,回答我们另外一个排序方法:堆排序。
堆排序也是很好的排序方法之一,如快排平均效率很高,但是最坏情况下仍然逃脱不了O(n^2)级(当数据已经有序时),但是堆排序在最坏情况下仍然坚挺,保持O(n*log(n))的高度。那我们就来说说它吧。
堆排序首先要建立堆,堆是一种特殊的数据结构:x[i/2]<=x[i]的就算具有堆属性。
堆的操作有两个关键操作,siftup 和siftdown (向上筛选,向下筛选 分别对应插入一个数据,修改堆顶数据).注:这里的堆用数组表示。
void siftup(int n) pre n>0 && heap(1,n-1) post heap(1,n) { tmp=x[i]; i=n; while(i>1) { if(x[i]>=x[i/2]) break; x[i]=x[i/2]; //swap(x[i],x[i/2); i=i/2; } x[i]=temp; } void siftdown(int n) pre heap(2,n) &&n>0; post heap(1,n) { i=1; c=2*i; while(c<=n) { if(c+1<=n) { if(x[c]>x[c+1]) c++; } if(x[c]>=x[i])break; swap(x[c],x[i]); i=c; c=2*i; } }
堆排序把数组看成两种抽象结构的结合:左边是堆,右边是已排序的元素序列。1...................i.....................n
首先建立堆:
for i=2..n//第一个已经是堆了 siftup(i)
然后建立有序序列:
for i=n;i>=2; i-- swap(1,i); siftdown(i-1);
综合以上可以写下如下的简短排序方法:
for(int i=2;i<=n;i++) siftup(i); for(int i=n;i>=2;i--) { swap(1,i); siftdown(i-1); }
每次按降序提取元素,这样建立从右到左的有序序列。n-1 次siftup 和siftdown ,每个操作最多O(logn),故时间是 O(nlogn),很好很强大啊。