排序算法之：最小差值排序（MinDiff Sort）的进阶应用：优化相邻元素最大差值问题

题目描述：给定一个未排序的整数数组，要求在线性时间和线性空间复杂度内，找到排序后相邻元素之间的最大差值。如果数组元素少于2个，返回0。这是最小差值排序（MinDiff Sort）的核心应用场景。

解题过程：

1. 问题分析

   • 直接思路：先排序后扫描，但基于比较的排序需要O(n log n)时间
   • 关键观察：最大差值一定不小于(最大值-最小值)/(n-1)
   • 核心思路：使用桶排序思想，但不需要完全排序整个数组

2. 算法设计

   • 步骤1：找到数组的最小值minVal和最大值maxVal
   • 步骤2：计算桶大小bucketSize = ceil((maxVal-minVal)/(n-1))
   • 步骤3：创建n个桶，每个桶记录区间内的最小值和最大值
   • 步骤4：将每个元素放入对应的桶：bucketIndex = (num-minVal)/bucketSize
   • 步骤5：遍历所有桶，用当前桶的最小值减去前一个非空桶的最大值

3. 关键证明

   • 最大差值不可能出现在同一个桶内（因为桶内最大差值小于bucketSize）
   • 最大差值一定出现在相邻的非空桶之间
   • 至少有一个桶为空时，最大差值一定大于bucketSize

4. 具体实现细节

   • 处理边界情况：n<2时直接返回0
   • 桶的数量设为n，确保至少有一个桶为空
   • 只需要记录每个桶的最小值和最大值，不需要存储所有元素

5. 复杂度分析

   • 时间复杂度：O(n) - 只需要遍历数组常数次
   • 空间复杂度：O(n) - 需要存储n个桶的信息

这个算法巧妙利用了鸽巢原理，通过桶的划分将问题转化为寻找桶间最大差值，避免了完全排序的开销。