from: http://blog.csdn.net/jwzbskywz/article/details/6995461
题目：有无序的实数列V[N]，要求求里面大小相邻的实数的差的最大值，关键是要求线性空间和线性时间
用基于桶排序的方式。
注意到，最后只需要求间隔的最大值，所以任何间隔小于bar= (max - min)/(N-1) 的值都可以不计。
这样，首先求随机数组中的max , min 这些都是线性时间的
然后，分配从[min, max]间分配(N-1)个桶，每个桶是一个有序实数对，(a,b)
将所有数往桶里塞，把欲塞进去的数记为x，如果桶里本身没有数，那么a=b=x
如果x>b，那么b=x,如果x <a那么a=x，反正就是说这个桶里的(a,b)表示进入该桶中的数的范围。此操作是线性的。
然后按顺序对每个相邻桶（跳过没有数的桶）进行比较。例如，相邻桶(a,b), (c,d)的距离D = 就是c - b
最终就是，比较的D的最大值。这时间也是线性的。空间也是线性的。
可能的问题：为什么我不必计算(b-a)或者(d-c)呢？很显然，b-a和d-c都是 <bar的，最大相邻间隔肯定是大于bar的。
代码：
#include <stdio.h>
int MaxDiff(int a[], int n)
{
int max, min, i;
max = min = a[0];
for (i=1; i < n; ++i)
{
if (a[i] > max)
max = a[i];
if (a[i] < min)
min = a[i];
}
int bar, pos;
bar = (max-min)/(n-1);
int (*bucket)[2] = new int[n][2](); //初始化数组 [0]放桶中最小 [1]放桶中最大值
memset(bucket, 0, n*2*sizeof(int));
for (i=0; i<n; ++i)
{
pos = (a[i]-min)/bar;
if (bucket[pos][0] == 0)
{
bucket[pos][0] = bucket[pos][1] = a[i];
}
else
{
if (a[i] > bucket[pos][1])
bucket[pos][1] = a[i];
if (a[i] < bucket[pos][0])
bucket[pos][0] = a[i];
}
}
int max_diff, diff;
max_diff = 0;
for (i=1; i<n; ++i)
{
if (bucket[i][0] != 0)
{
diff = bucket[i][0] - bucket[i-1][1];
if (max_diff < diff)
max_diff = diff;
}
}
delete[] bucket;
return max_diff;
}
int main()
{
int b[] = {3, 89, 76, 23, 23, 87};
printf("%d", MaxDiff(b, 4));
return 0;
}