| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1307 人关注过本帖
标题:[求助] 介绍一下这几个算法
只看楼主 加入收藏
herbert_1987
Rank: 5Rank: 5
等 级:贵宾
威 望:15
帖 子:1314
专家分:0
注 册:2007-5-13
收藏
 问题点数:0 回复次数:10 
[求助] 介绍一下这几个算法
1 桶排序
2 红黑树
3 区间树
4 贪心算法
5 B树
6 二项堆
7 斐波那契堆
8 Bellman-Ford 算法
9 Dijkctrq 算法
10 Floyd-warshill 算法
11 Johnson 算法
12 流网络
13 排序网络
14 NP 完全性
15 近似算法

熟悉这些算法的朋友,麻烦介绍一下这些算法
及其用处,谢谢!
搜索更多相关主题的帖子: 算法 网络 Johnson 完全性 
2007-06-18 12:50
HJin
Rank: 6Rank: 6
等 级:贵宾
威 望:27
帖 子:401
专家分:0
注 册:2007-6-9
收藏
得分:0 

1. bucket sort is something that you assume your input is between [0, 1), and each input is equally likely distributed into, say, m intervals. Following is my implementation of the algorithm as it is described in Cormen's book.

#include <iostream>
#include "hjns.h"
#include <list>
#include <algorithm>
#include <vector>


using namespace std;

void bucketsort(double* a, int n);

int main(int argc, char** argv)
{
const int kSize = 13;
double a[kSize];
hj::number::random rd;
int i;

for(i=0; i<kSize; ++i)
a[i] = rd(1);
vector<double> vd(a, a+kSize);
sort(vd.begin(), vd.end());

hj::print(a, kSize);
hj::print(vd);

bucketsort(a, DIM(a));
hj::print(a, DIM(a));

for(i=0; i<DIM(a); ++i)
{
if(vd[i] != a[i])
{
cout<<"unsuccessful: "<<vd[i]<<" "<<a[i]<<endl;
break;
}
}

return 0;
}

void bucketsort(double* a, int n)
{
list<double>* B = new list<double>[n];
int i;

for(i=0; i<n; ++i)
B[int(n*a[i])].push_back(a[i]);

for(i=0; i<n; ++i)
B[i].sort();

for(i=1; i<n; ++i)
B[0].splice(B[0].end(), B[i]);

i=0;
for(list<double>::const_iterator it = B[0].begin(); it != B[0].end(); ++it)
{
a[i] = *it;
++i;
}

delete [] B;
}


I am working on a system which has no Chinese input. Please don\'t blame me for typing English.
2007-06-18 17:44
herbert_1987
Rank: 5Rank: 5
等 级:贵宾
威 望:15
帖 子:1314
专家分:0
注 册:2007-5-13
收藏
得分:0 

谢谢楼上, 研究一下先.


人生重要的不是所站的位置,而是所朝的方向
2007-06-18 18:42
yixiliuyun
Rank: 1
等 级:新手上路
帖 子:14
专家分:0
注 册:2007-6-16
收藏
得分:0 
这是什么算法阿??

我的qq算法群 供大家讨论哦 请各位喜欢算法的朋友加入哦 qq群号 40320457 嘿嘿
2007-06-19 11:52
killer_l
Rank: 2
等 级:新手上路
威 望:3
帖 子:1139
专家分:0
注 册:2007-5-25
收藏
得分:0 
纯英文的大叔

2007-06-19 12:03
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
收藏
得分:0 

桶排序 Bin Sort
平均情况下桶排序以线性时间运行。像计数排序一样,桶排序也对输入作了某种假设, 因而运行得很快。具体来说,计数排序假设输入是由一个小范围内的整数构成,而桶排序则 假设输入由一个随机过程产生,该过程将元素一致地分布在区间[0,1)上。

桶排序的思想就是把区间[0,1)划分成n个相同大小的子区间,或称桶,然后将n个输入数分布到各个桶中去。因为输入数均匀分布在[0,1)上,所以一般不会有很多数落在 一个桶中的情况。为得到结果,先对各个桶中的数进行排序,然后按次序把各桶中的元素列 出来即可。

在桶排序算法的代码中,假设输入是个含n个元素的数组A,且每个元素满足0≤ A[i]<1。另外还需要一个辅助数组B[O..n-1]来存放链表实现的桶,并假设可以用某种机制来维护这些表。

桶排序的算法如下,其中floor(x)是地板函数,表示不超过x的最大整数。

procedure Bin_Sort(var A:List);
begin
1 n:=length(A);
2 for i:=1 to n do
3 将A[i]插到表B[floor(n*A[i])]中;
4 for i:=0 to n-1 do
5 用插入排序对表B[i]进行排序;
6 将表B[0],B[1],...,B[n-1]按顺序合并;
end;


倚天照海花无数,流水高山心自知。
2007-06-19 13:49
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
收藏
得分:0 
个人觉得和基数排序的思想差不多.

倚天照海花无数,流水高山心自知。
2007-06-19 13:50
herbert_1987
Rank: 5Rank: 5
等 级:贵宾
威 望:15
帖 子:1314
专家分:0
注 册:2007-5-13
收藏
得分:0 
知道了, 谢谢nuciewth!

人生重要的不是所站的位置,而是所朝的方向
2007-06-20 10:42
herry
Rank: 1
等 级:新手上路
帖 子:43
专家分:0
注 册:2007-5-26
收藏
得分:0 
厉害
2007-06-23 15:02
ACKing
Rank: 1
等 级:新手上路
帖 子:69
专家分:0
注 册:2007-9-4
收藏
得分:0 
9 Dijkctrq 算法
10 Floyd-warshill 算法

......学好英文先。。。。这样子写 地下的牛人都会被你气活的。。。。
2007-09-20 14:46
快速回复:[求助] 介绍一下这几个算法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017141 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved