排序算法之：最小差值排序（MinDiff Sort）

题目描述
给定一个长度为 n 的整数数组 arr，我们需要通过交换相邻元素的方式对数组进行排序，使得排序完成后的数组中，相邻元素差值的最大值最小。换句话说，在通过交换相邻元素（即每次只能交换相邻两个数）的排序过程中，我们关心的是在最终的有序状态下，数组中任意两个连续元素之间的差值，找出这些差值中的最大值，并确保这个最大值是所有可能的相邻交换排序结果中最小的。

但仔细分析会发现，如果只允许交换相邻元素进行排序，那么最终排序结果必然是完全升序（或降序）的数组，因为这就是冒泡排序的最终状态。那么相邻元素差值的最大值也就确定了，就是排序后相邻元素的最大差值。因此，更一般的理解是：
先对数组进行排序（不限于相邻交换，可采用任何排序方法得到完全有序数组），然后计算排序后相邻元素差值的最大值，并验证这个最大值是否能通过相邻交换操作实现排序的过程中得到控制？ 实际上，MinDiff Sort 关注的是排序过程中“相邻差值”的优化，而不是单纯排序。但这里我们聚焦于在完全排序后，相邻元素差值的最大值的计算与优化，这是许多算法问题的核心步骤。

为了简化，我们明确题目：
给定一个数组，返回其排序后相邻元素差值的最大值。 我们需要高效求解这个最大值。

输入：一个整数数组 arr，长度 n ≥ 2。
输出：排序后相邻元素差值的最大值。

示例：
输入：[3, 6, 9, 1]
排序后：[1, 3, 6, 9]
相邻差值：2, 3, 3，最大值是 3。
输出：3。

解题过程

步骤 1：问题转化
要计算“排序后相邻元素差值的最大值”，最直接的方法是：

1. 对数组进行排序。
2. 遍历排序后的数组，计算相邻元素的差值。
3. 记录并返回最大差值。

这种方法的时间复杂度取决于排序的复杂度，通常为 O(n log n)。
但有没有可能在线性时间内解决？
当元素是整数且范围已知时，可以使用桶排序的思路来优化，但通用情况下，基于比较的排序下界是 O(n log n)，因此通常认为 O(n log n) 是理论最优的。不过，如果仅仅为了求最大差值，我们可以在排序后一次性扫描得到，不需要额外优化，因为扫描是 O(n)。

所以核心步骤是：排序 + 扫描。

步骤 2：选择排序算法
对于任意可比较的数据，我们可以用快速排序、归并排序、堆排序等。
这里以归并排序为例，因为其时间复杂度稳定为 O(n log n)，且适合教学。

归并排序的步骤：

1. 如果数组长度 ≤ 1，直接返回。
2. 将数组从中间分成左右两半。
3. 递归对左半部分排序。
4. 递归对右半部分排序。
5. 合并两个有序子数组。

合并过程（merge）：

• 创建一个临时数组，依次从左右子数组中选取较小的元素放入，直到某个子数组用完，将另一个子数组剩余部分接在后面。

步骤 3：实现排序
以下是归并排序的伪代码，用于将数组排成升序：

function mergeSort(arr, left, right):
    if left >= right:
        return
    mid = left + (right - left) / 2
    mergeSort(arr, left, mid)
    mergeSort(arr, mid+1, right)
    merge(arr, left, mid, right)

function merge(arr, left, mid, right):
    // 创建临时数组存放 left..right 的元素
    temp = new array[right-left+1]
    i = left, j = mid+1, k = 0
    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp[k] = arr[i]; i++; k++
        else:
            temp[k] = arr[j]; j++; k++
    // 拷贝剩余部分
    while i <= mid:
        temp[k] = arr[i]; i++; k++
    while j <= right:
        temp[k] = arr[j]; j++; k++
    // 将 temp 拷贝回 arr[left..right]
    for p in 0 .. k-1:
        arr[left+p] = temp[p]

步骤 4：计算最大相邻差值
排序后，遍历数组一次：

function maxSortedAdjacentDiff(arr):
    n = length(arr)
    if n < 2:
        return 0
    sort(arr)  // 使用归并排序
    maxDiff = 0
    for i from 1 to n-1:
        diff = arr[i] - arr[i-1]
        if diff > maxDiff:
            maxDiff = diff
    return maxDiff

注意：如果数组元素可能为负数，差值应取绝对值，但排序后升序，arr[i] - arr[i-1] 自然非负。

步骤 5：边界情况

• 数组长度 n=2：排序后直接计算差值。
• 有重复元素：差值可能为 0，不影响最大差值的计算。
• 元素值非常大：注意使用足够大的整数类型存储差值。

步骤 6：复杂度分析

• 时间复杂度：排序 O(n log n)，扫描 O(n)，总复杂度 O(n log n)。
• 空间复杂度：归并排序需要 O(n) 的临时数组空间。

步骤 7：优化思路（附加）
如果题目允许使用非比较排序，且数组元素是整数且范围不大，可以用计数排序或基数排序达到 O(n) 时间，然后扫描。
例如，假设元素范围已知且较小：

1. 找出数组的最小值 min 和最大值 max。
2. 创建长度为 (max-min+1) 的计数数组。
3. 统计每个元素出现次数。
4. 根据计数数组重建有序数组。
5. 扫描计算最大相邻差值。

但若元素范围很大，计数数组可能过大，此时基数排序可以在 O(nk) 时间内完成（k 是最大数字的位数）。

步骤 8：举例演示
以 [1, 5, 3, 9, 2] 为例：

1. 排序：归并排序过程（略），得到 [1, 2, 3, 5, 9]。
2. 计算相邻差值：1和2差1，2和3差1，3和5差2，5和9差4。
3. 最大差值 = 4。

最终输出 4。

总结
最小差值排序问题实质上是在求“排序后相邻元素的最大差值”，关键在于先进行排序，再线性扫描。使用归并排序可保证稳定高效的排序，整体复杂度 O(n log n)。如果追求线性时间，可在特定条件下使用非比较排序。