2 红黑树
3 区间树
4 贪心算法
5 B树
6 二项堆
7 斐波那契堆
8 Bellman-Ford 算法
9 Dijkctrq 算法
10 Floyd-warshill 算法
11 Johnson 算法
12 流网络
13 排序网络
14 NP 完全性
15 近似算法
熟悉这些算法的朋友,麻烦介绍一下这些算法
及其用处,谢谢!
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;
}
桶排序 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;