一个优化的堆排序

每次降序提取元素建立从右到左的有序序列
服务器君一共花费了349.228 ms进行了4次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

如何生成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()0]);
        a[m] = i;
}

该方法效率不高(因为很可能生成重复的位置),该章后面的原理部分很好:

  1. 正确理解你所遇到的问题
  2. 提炼抽象问题
  3. 考虑尽可能多的解法
  4. 实现一种解决方案

这些建言真的很不错,思考的时间和深度是和解决问题的力度成正比的。

好,说完题外话,回答我们另外一个排序方法:堆排序。

堆排序也是很好的排序方法之一,如快排平均效率很高,但是最坏情况下仍然逃脱不了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),很好很强大啊。

本文地址:http://www.nowamagic.net/librarys/veda/detail/1169,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1169

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《浪潮之巅》 吴军 (作者)

近一百多年来,总有一些公司很幸运地、有意识或无意识地站在技术革命的浪尖之上。在长达十年甚至几十年的时间里,它们代表着科技的浪潮,直到下一波浪潮的来临。从19世纪末算起,AT&T公司、IBM公司、苹果公司、英特尔公司、微软公司、思科公司、雅虎公司和Google公司都先后被幸运地推到了浪尖。虽然,它们来自不同的领域,中间有些已经衰落或正在衰落,但是它们都极度辉煌过。吴军的这本《浪潮之巅》系统地介绍了这些公司成功的本质原因及科技工业一百多年的发展。在这些公司兴衰的背后,有着它必然的规律。《浪潮之巅》不仅讲述科技工业的历史,更重在揭示它的规律性。

更多计算机宝库...