一个无序整型数组，求出该数组排序后任意两个相邻元素的最大差值。
时间复杂度：O(nlogn) 这是最简单的方案，随便找一个时间复杂度O(nlogn)的排序算法，排好序后遍历一轮即可找到最大差值。
时间复杂度：O(n) 计数排序利用数组下标找到元素值，可把时间复杂度降到O(n)。 同样是先排序，后统计找到哪两个元素在数组间空了最多空位即为最大差值。
时间复杂度：O(n) 之所以会用到桶排序，是因为计数排序有其局限性。
当元素差值过大时，如1，2，10000。 需要申请的辅助空间过于庞大！
桶排序的思路是根据原始序列长度n，创建n+1个桶。 根据序列max、min值平均划分每个桶的区间。
而每个桶只需要记录桶内的最大最小值即可。
最后遍历所有桶，计算 当前桶的max 与 下个非空桶的min 之间的差值，最大即所求。
以上三种思路都非常好理解，只要熟悉基本的排序算法的话。
但是仔细思考，桶排序似乎有些疑点🤔️：
这一定是爱思考的人避不开的问题！
我们来举个例子，会比较形象一点：
A = {0,45,47,27,22,31,83,23,99}可得信息：
n = 9min = 0max = 99根据第三种思路，我们创建10个桶(9+1)。
这就是这个算法的巧妙之处了，也是为什么最大相邻差必定在桶间的原因！
由于我们只有9个元素，而桶却有10个。也就是说，必然存在一个空桶！ 桶内最大的差值是9，而空桶两边相邻非空桶之间最大差值最小情况为11！
用白话说就是，怎么着也轮不到你桶内是最大！😎
综上所述，也就是由于桶的数量取n+1，保证了最大相邻差一定是在桶间！
如果对您有帮助的话，请点个赞吧！！ 😋😋
