本文介绍一种通过检测相邻元素方向变化（升序/降序切换）来识别数组中连续单调子序列，并对每个子序列独立排序的高效算法，适用于处理如 [53,50,41,8,64,35,17,...] 这类含多段递减/递增片段的数组。
本文介绍一种通过检测相邻元素方向变化（升序/降序切换）来识别数组中连续单调子序列，并对每个子序列独立排序的高效算法，适用于处理如 `[53,50,41,8,64,35,17,...]` 这类含多段递减/递增片段的数组。
在给定数组中提取“自然单调段”（即连续递增或连续递减的最长子序列），然后对每一段分别升序排序，是典型的分段单调识别与局部排序问题。关键在于：不能仅依赖全局趋势或单向扫描计数（如原代码中仅统计下降长度），而应以方向切换点为分界标志——当序列从递减变为递增，或从递增变为递减时，即意味着前一段单调性终止，需立即截断并排序。
核心思想：有限状态机驱动的分段识别
算法本质是一个双状态跟踪器：维护 was_up（前一对是否升序）和 was_down（前一对是否降序），结合当前 up/down 判断方向是否翻转：
- 若 (was_up && down) → 由升转降，前一段递增结束；
- 若 (was_down && up) → 由降转升，前一段递减结束；
此时触发排序：对 data[ldx] 到 data[i]（含）的闭区间子数组升序排序，并重置 ldx = i + 1，开始新段。
✅ 注意：ldx 始终指向当前待处理段的起始索引；最后一段需在循环外补排序（因无后续方向变化触发）。
Java 实现示例（适配原问题场景）
import java.util.*;
public class MonotonicSegmentSort {
public static void sortMonotonicSegments(int[] arr) {
if (arr == null || arr.length arr[i + 1];
// 方向发生翻转：升→降 或 降→升
if ((wasUp && down) || (wasDown && up)) {
Arrays.sort(arr, ldx, i + 1); // 排序 [ldx, i]（左闭右开，故 i+1）
ldx = i + 1;
wasUp = wasDown = false;
} else {
wasUp = up;
wasDown = down;
}
}
// 排序最后一段
Arrays.sort(arr, ldx, arr.length);
}
// 测试用例
public static void main(String[] args) {
int[] data = {53, 50, 41, 8, 64, 35, 17, 76, 58, 3, 75, 1, 99, 56, 2};
sortMonotonicSegments(data);
System.out.println(Arrays.toString(data));
// 输出: [8, 41, 50, 53, 17, 35, 64, 3, 58, 76, 1, 75, 2, 56, 99]
}
}
关键注意事项
- 边界鲁棒性：空数组、单元素、全等元素（up=false && down=false）均被正确跳过，不触发排序；
- 排序稳定性：Arrays.sort() 对基本类型采用双轴快排，时间复杂度平均 O(n log n)，但每段独立排序，总开销取决于段数与长度分布；
- 原地操作：无需额外集合存储索引，空间复杂度 O(1)（除排序栈空间）；
- 逻辑陷阱规避：原代码错误在于仅追踪“最长下降段”，却忽略方向切换才是分段本质——例如 [64,35,17] 后接 76（上升），必须在此处分割，而非继续寻找更长下降序列。
该方法将问题抽象为状态迁移过程，简洁、可扩展（如支持自定义排序规则或保留原始段信息），是处理此类“隐式分段排序”任务的通用范式。
