本文介绍如何在不使用额外数组或集合的前提下，将两个固定长度的数组视为整体进行升序排序，并按原始长度约束重新分配元素——即实现真正原地（in-place）的双数组联合排序与分割。
本文介绍如何在不使用额外数组或集合的前提下，将两个固定长度的数组视为整体进行升序排序，并按原始长度约束重新分配元素——即实现真正原地（in-place）的双数组联合排序与分割。
要满足“零额外空间”“不改变数组长度”“联合升序排列”三大约束，关键在于放弃“先合并再拆分”的思维惯性（如用 List 中转），转而采用原地归并思想 + 分治调整策略。核心思路是：
- 分别排序两数组 → 获得局部有序基础；
-
视作一个逻辑长数组（
arr1[0..m-1] + arr2[0..n-1]），通过类似归并排序的“逆向填充”方式，将全局最小的m个元素归位到arr1，其余n个归位到arr2； - 整个过程仅使用常数级额外变量（O(1) 空间），无任何动态集合或临时数组。
以下是完整、可运行的 Java 实现：
import java.util.Arrays;
public class InPlaceTwoArraySort {
public static void sortAndSplit(int[] arr1, int[] arr2) {
// Step 1: 单独排序两个数组（原地）
Arrays.sort(arr1);
Arrays.sort(arr2);
int m = arr1.length;
int n = arr2.length;
// Step 2: 归并准备 —— 使用三指针法从后往前“选择”全局最大元素
// 目标：让 arr1 最终存放全局最小的 m 个元素，arr2 存放剩余 n 个
// 我们反向构建：从逻辑末尾（位置 m+n-1）开始，将当前最大值放入正确位置
// 但注意：我们不能新建数组，因此需在 arr1 和 arr2 内部交换/移动元素
// 更稳健且符合题意的方案：使用「循环移位+二分定位」实现原地重分布
// 策略：将 arr1 和 arr2 视为一个环形缓冲区，通过多次旋转将前 m 小元素“挤入”arr1
// ✅ 推荐解法：双指针归并 + 原地覆盖（需辅助函数 rotate）
// 先将 arr2 合并到 arr1 末尾？不行——arr1 长度固定，不可扩容。
// 正确路径：利用 arr1 的“冗余容量”暂存，但 arr1 容量已满 → 改用「就地归并分割」算法：
// ✔ 最优实践：采用「两数组归并 + 反向填充分割」（无需额外空间）
// 思路：已知最终 arr1 应含最小 m 个，arr2 含最大 n 个。
// 我们可在 arr1 和 arr2 上模拟归并过程，用一个临时变量做“搬运工”，逐个将应属 arr1 的小元素换入，把大元素“踢”进 arr2。
// 实际高效解法（经典原地合并变体）：
int i = 0, j = 0, k = 0; // i: arr1 当前索引, j: arr2 当前索引, k: 全局计数器（目标位置）
while (k idx; i--) {
arr2[i] = arr2[i-1];
}
arr2[idx] = value;
}
// ✅ 生产环境推荐的简洁解法（完全符合题意）：
public static void sortTwoArraysInPlace(int[] arr1, int[] arr2) {
// 1. 分别排序（O(m log m + n log n)）
Arrays.sort(arr1);
Arrays.sort(arr2);
// 2. 归并两个有序数组，但不新建数组 —— 而是用「双指针 + 交换」将前 m 小元素“沉淀”到 arr1
// 使用标准库 Arrays.binarySearch 定位分界点（全局第 m 小元素值）
// 构造合并后的逻辑数组（不实际创建）→ 利用二分搜索 + 计数确定阈值
int m = arr1.length, n = arr2.length;
int total = m + n;
int targetRank = m; // arr1 应容纳最小的 targetRank 个元素
// 二分搜索候选阈值（在 arr1 和 arr2 值域内）
int left = Math.min(arr1[0], arr2[0]);
int right = Math.max(arr1[m-1], arr2[n-1]);
while (left threshold 的归入 arr2；对边界相等情况按需调整数量
int smallCount = countLessEqual(arr1, threshold) + countLessEqual(arr2, threshold);
int needFromArr2 = Math.max(0, m - countLessEqual(arr1, threshold));
// 实际执行：遍历 arr2，将较小元素交换进 arr1，较大元素留下
int writeIdx = 0;
for (int i = 0; i <p><strong>注意事项与总结：</strong> </p>
- ❗ 绝对避免
List中转或stream().sorted()—— 这会创建新对象，违反“零额外空间”要求； - ✅
Arrays.sort()是安全的，它基于双轴快排/归并，原地操作，符合空间约束； - ? 真正的挑战在于重分布：排序后需将全局最小
m个元素精准落入arr1，这需结合二分搜索定位阈值 + 双指针交换实现； - ⚠️ 若面试场景，可先给出
Arrays.sort()+binarySearch+arraycopy的框架思路（如答案中提示），再补充关键步骤说明； - ? 时间复杂度：O(m log m + n log n + (m+n) log(max-min))，空间复杂度：O(1)，完全满足题目全部硬性约束。
掌握该方法，不仅解决双数组排序问题，更深入理解了原地算法设计的核心——用时间换空间，以逻辑重组替代物理复制。
