1. 题目到底在考什么——先读懂“原有规律”这四个字这个题目在Java面试和课后作业里出现的频率极高但绝大多数人只记住了“插入”两个字忽略了“原有规律”这个前提。说实话这个细节才是整道题的核心考点。先把这个需求用大白话翻译一下你手里有一个已经排好序的数组比如从小到大排列的{1, 3, 5, 7, 9}现在给你一个数字比如6你需要把它插进去插入之后数组仍然是排好序的最终得到{1, 3, 5, 6, 7, 9}。听起来很简单但注意三个坑第一个坑数组的长度是固定的。Java里数组一旦创建长度就不能变了所以“插入”这个操作本质上不是真的往原数组里塞而是创建一个新数组把元素搬过去。这是Java数组和链表最本质的区别也是面试官最爱追问的点。第二个坑“原有规律”不一定是升序。有可能给你的数组是降序排列的也有可能数组里存在重复元素比如{1, 3, 3, 5}。这些情况都会影响插入位置的判断逻辑。第三个坑判断插入位置的边界条件。插入的数可能比数组里所有数都小也可能比所有数都大还需要处理正好等于某个元素的情况——是插在前面还是后面这块写不好就很容易出现数组越界或者位置错乱。这道题适合Java初学者巩固数组操作也适合准备面试的人复习二分查找、System.arraycopy这些基础API。下面我把整个解题过程从简单到复杂拆开讲每一步都给出可直接运行的代码顺便把我自己踩过的坑也一并说清楚。2. 先跑通基础方案顺序扫描定位插入点2.1 核心思路最直觉的做法就是从数组的第一个元素开始一个一个往后找找到第一个比待插入数大或相等的位置这个位置就是插入点。然后把插入点后面的所有元素往后挪一格腾出位置再把目标数放进去。具体分三步第一步遍历数组找到插入位置。第二步创建新数组长度在原数组基础上加1。第三步分三段拷贝——插入点之前的元素、插入的目标数、插入点之后的元素。这个方法时间复杂度是O(n)因为找位置需要遍历一次拷贝数组本质上又是遍历一次。空间复杂度是O(n)因为创建了新数组。2.2 完整实现代码public class InsertIntoSortedArray { public static int[] insert(int[] arr, int target) { // 边界情况原数组为空直接返回只含target的数组 if (arr null || arr.length 0) { return new int[]{target}; } // 第一步寻找插入位置 int insertPos arr.length; // 默认插到最后 for (int i 0; i arr.length; i) { // 升序数组找到第一个 target 的位置 if (arr[i] target) { insertPos i; break; } } // 第二步创建新数组长度为原长度 1 int[] result new int[arr.length 1]; // 第三步拷贝插入点之前的元素 for (int i 0; i insertPos; i) { result[i] arr[i]; } // 放置目标数 result[insertPos] target; // 拷贝插入点之后的元素 for (int i insertPos; i arr.length; i) { result[i 1] arr[i]; } return result; } public static void main(String[] args) { int[] arr {1, 3, 5, 7, 9}; int target 6; int[] result insert(arr, target); for (int num : result) { System.out.print(num ); } // 输出1 3 5 6 7 9 } }这段代码我建议你亲手敲一遍不要直接复制。敲的过程中你会注意到几个关键判断arr[i] target这个条件为什么用而不是这是决定重复元素插入位置的核心逻辑。用时遇到相等元素会插在它前面用时会插在它后面。两种写法都能保证数组仍然有序但结果不同。面试时如果主动说清楚这一点会显得你考虑问题很全面。2.3 边界情况从头到尾梳理写这段代码的时候我第一次跑就翻车了问题出在边界情况上。如果你没留意大概率也会踩同样的坑。情况一目标数比数组第一个元素还小比如数组{3, 5, 7}目标1。遍历时第一个元素3就已经满足3 1插入位置是0然后拷贝逻辑正常执行结果{1, 3, 5, 7}。没问题。情况二目标数比数组最后一个元素还大比如数组{3, 5, 7}目标9。遍历完整个数组都没找到比9大的元素这时候insertPos必须保持初始值arr.length也就是数组末尾。如果初始值你写的是0那结果就是错的——9会被放到第一个位置整个数组乱套。这里是最容易出错的地方记住insertPos的默认值永远是数组长度。情况三目标数等于数组中间某个元素数组{1, 3, 3, 5}目标3。用判断时插入位置是第一个3的位置下标1插入后变成{1, 3, 3, 3, 5}。新插入的3在原来两个3的前面。用判断时插入位置是第二个3的位置下标2变成{1, 3, 3, 3, 3, 5}新插入的3在后面。两种结果都符合“与原有规律一致”的要求。我建议初学者把这三个边界情况写成测试用例逐个跑一遍比看十遍理论都有用。3. 升级版需求兼容升序和降序的动态排序规律3.1 为什么很多人的代码在降序数组上直接崩了有读者留言问我“题目说的是按原有规律我们班作业给的数组是降序的用你上面的代码跑出来结果是错的。”确实上面那段代码只考虑了升序场景。而实际项目中数据的排序规律往往不是我们能控制的可能来自配置文件可能来自外部接口。要兼容降序核心改动只有一个地方比较逻辑反过来。降序数组中应该找到第一个 target的元素作为插入位置。但代码不能写死最好先判断一下原数组到底是升序还是降序。3.2 通用版代码自动识别排序方向public static int[] insertPreservingOrder(int[] arr, int target) { if (arr null || arr.length 0) { return new int[]{target}; } // 判断排序方向比较首尾元素即可 boolean ascending arr[0] arr[arr.length - 1]; int insertPos arr.length; for (int i 0; i arr.length; i) { if (ascending) { // 升序找第一个 target 的位置 if (arr[i] target) { insertPos i; break; } } else { // 降序找第一个 target 的位置 if (arr[i] target) { insertPos i; break; } } } int[] result new int[arr.length 1]; for (int i 0; i insertPos; i) { result[i] arr[i]; } result[insertPos] target; for (int i insertPos; i arr.length; i) { result[i 1] arr[i]; } return result; }判断升降序我直接用首元素和尾元素比较因为一个正确的排序数组首尾大小关系就已经能反映整体方向了。这种写法的好处是完全不需要额外扫描一遍数组O(1)时间搞定。这里还有一个隐藏知识点如果数组只有一个元素arr[0] arr[arr.length - 1]会变成元素自己跟自己比结果是false默认走降序逻辑。但这不影响结果因为单元素数组不管升序降序插入逻辑都一样——要么插前面要么插后面最终数组都是两个元素且有序。不过为了严谨你可以在判断前加上arr.length 1的条件。3.3 如果要处理对象怎么办实际开发中数组里存的往往不是int而是对象。比如一个User类按年龄排序。这种场景下“原有规律”就要靠Comparable或Comparator来定义了。public static User[] insertUser(User[] arr, User target, ComparatorUser comparator) { if (arr null || arr.length 0) { return new User[]{target}; } int insertPos arr.length; for (int i 0; i arr.length; i) { // comparator.compare 返回负数表示 arr[i] 在 target 前面 if (comparator.compare(arr[i], target) 0) { insertPos i; break; } } User[] result new User[arr.length 1]; System.arraycopy(arr, 0, result, 0, insertPos); result[insertPos] target; System.arraycopy(arr, insertPos, result, insertPos 1, arr.length - insertPos); return result; }看到这里你大概明白了compare方法的返回值本质上就是在帮我们描述“谁应该排在谁前面”。这是Java排序体系的底层逻辑不但这个题目用得到Arrays.sort()、TreeMap、PriorityQueue这些地方全都在用同一套规则。理解了这一点你就把“插入有序数组”这个小题目和Java整个排序体系打通了。4. 数组扩容的后半段System.arraycopy 到底怎么用4.1 为什么推荐用它而不是自己写for循环前面写的代码为了易懂拷贝数组用的是for循环。但真实项目里我强烈建议用System.arraycopy。它是一个native方法由JVM底层直接操作内存拷贝性能比手动循环高得多而且代码也更简洁不容易出错。System.arraycopy 方法有五个参数很多初学者记不住顺序我总结了一个记忆口诀从哪来、从哪开始、到哪去、从哪开始、拷几个。System.arraycopy( 源数组, // 从哪来 源起始位置, // 源数组从第几个开始拷 目标数组, // 到哪去 目标起始位置, // 目标数组从第几个开始放 拷贝长度 // 拷几个 );拿插入操作来说需要两次拷贝。插入点之前的部分从源数组第0个拷到目标数组第0个拷insertPos个元素。插入点之后的部分从源数组第insertPos个拷到目标数组第insertPos1个拷arr.length - insertPos个元素。4.2 用 System.arraycopy 改造后的完整版本public static int[] insertWithArraycopy(int[] arr, int target) { if (arr null || arr.length 0) { return new int[]{target}; } int insertPos arr.length; for (int i 0; i arr.length; i) { if (arr[i] target) { insertPos i; break; } } int[] result new int[arr.length 1]; // 第一段插入位置之前的元素 System.arraycopy(arr, 0, result, 0, insertPos); // 中间插入目标元素 result[insertPos] target; // 第二段插入位置之后的元素 System.arraycopy(arr, insertPos, result, insertPos 1, arr.length - insertPos); return result; }写System.arraycopy的时候有一个最典型的错误最后一个参数写错导致ArrayIndexOutOfBoundsException。比如第二段拷贝源数组从insertPos开始到末尾总共应该有arr.length - insertPos个元素。如果你写成了arr.length - insertPos 1就会越界。这个 1 和 -1 的细节特别容易搞混。4.3 为什么不直接用 Arrays.copyOf 一步到位有人可能会问Java 提供了Arrays.copyOf能不能直接用它来扩容当然可以Arrays.copyOf(arr, arr.length 1)能快速得到一个长度1的新数组后半部分自动补0。但这只解决了“扩容”问题没有解决“插入位置”问题——你还需要手动把插入点之后的元素再往后挪一位。所以更优雅的组合是Arrays.copyOf先扩容再用System.arraycopy把后半段往后挪。不过说实话对于这道题直接用两次System.arraycopy已经足够清晰了没必要再套一层。保持代码简单是资深开发者非常看重的品质。5. 二分查找定位插入位置——别再线性扫描了5.1 什么时候必须用二分线性扫描的代码虽然正确但数据量一大就露馅。假设一个数组有100万个元素要在其中插入一个数平均需要比较50万次。如果频繁执行插入操作性能完全不可接受。二分查找的核心优势是每次比较都能排除一半的元素。100万个元素里查找一个位置最多只需要比较20次因为2的20次方约等于100万。这个差距是指数级的。但二分查找有一个前提数组必须已经是有序的。本题目恰好满足这个条件所以不二分白不二分。5.2 二分插入的模板写法public static int[] insertWithBinarySearch(int[] arr, int target) { if (arr null || arr.length 0) { return new int[]{target}; } // 二分查找插入位置升序场景 int left 0; int right arr.length; while (left right) { int mid (left right) 1; if (arr[mid] target) { left mid 1; } else { right mid; } } int insertPos left; int[] result new int[arr.length 1]; System.arraycopy(arr, 0, result, 0, insertPos); result[insertPos] target; System.arraycopy(arr, insertPos, result, insertPos 1, arr.length - insertPos); return result; }注意几个细节全都是我踩过的坑第一个坑(left right) 1和(left right) / 2到底有什么区别。当left和right都是很大的正整数时它们的和可能超过int上限变成负数/ 2就会得到错误结果。是无符号右移能避免这个问题。最早的二分查找实现用(left right) / 2后来JDK官方都改成了(left right) 1的写法。虽然在这个题目的数组长度范围内不太可能溢出但好习惯要尽早养成。第二个坑终止条件left right而不是left right。这个模板使用的是左闭右开区间[left, right)初始时right arr.length而不是arr.length - 1。当arr[mid] target时说明目标数在右半区左边界收缩到mid 1否则目标数在左半区包括mid位置右边界收缩到mid。循环结束时left right这个位置就是插入点。这套模板是Java的Arrays.binarySearch内部实现思路背下来不会错。第三个坑二分查找的时间复杂度是O(log n)但插入数组本身因为要移动元素整体时间复杂度仍然是O(n)。很多面试者会在这里被问住。二分查找只是把“找位置”从O(n)优化到了O(log n)但System.arraycopy移动元素依然是O(n)。所以整体时间复杂度是O(n)。想彻底变成O(1)插入得换数据结构——这就要聊到链表了。5.3 二分版完整测试public static void main(String[] args) { int[] arr {1, 3, 5, 7, 9, 11, 13, 15}; int target 10; int[] result insertWithBinarySearch(arr, target); System.out.println(Arrays.toString(result)); // 输出[1, 3, 5, 7, 9, 10, 11, 13, 15] // 边界测试插入比所有元素都小的数 int[] result2 insertWithBinarySearch(arr, 0); System.out.println(Arrays.toString(result2)); // 输出[0, 1, 3, 5, 7, 9, 11, 13, 15] // 边界测试插入比所有元素都大的数 int[] result3 insertWithBinarySearch(arr, 100); System.out.println(Arrays.toString(result3)); // 输出[1, 3, 5, 7, 9, 11, 13, 15, 100] }这三个测试跑通了基本可以确认二分版本没问题。6. 面试官真正想听的这道题的三层延伸6.1 为什么用数组而不用链表——数据结构取舍面试官在你答完这道题之后十有八九会追问一句“数组插入元素要移动后面的所有元素性能不好那有没有更好的数据结构”这时候你要能自然地接上链表的插入操作时间复杂度是O(1)。在已知插入位置的前提下链表只需要修改前后节点的指针指向不需要搬动任何元素。但链表也有代价——查找插入位置的时间复杂度是O(n)而且内存占用更大每个节点要额外存指针对CPU缓存也不友好节点在内存中不一定连续。所以没有绝对的好坏只有合不合适。如果插入操作特别多且数据量巨大用链表。如果查找和随机访问更多用数组。面试时能把这个取舍讲清楚基本就能过关。6.2 从“插入一个数”到“批量插入”——动态扩容策略如果面试继续追问“如果连续插入100万个元素每次都创建一个新数组性能能接受吗”这就引出了动态扩容的话题也就是ArrayList的实现原理。ArrayList底层也是数组但它不会每次插入都创建新数组。而是提前预留容量当容量不够时才按1.5倍扩容。扩容需要拷贝旧数组到新数组所以最坏情况下单次插入是O(n)但均摊下来接近O(1)。这就是“均摊复杂度”的概念Java里ArrayList的add方法用的就是这个策略。理解了这点你再看ArrayList的源码会豁然开朗为什么ensureCapacity那么重要为什么add方法要先检查容量为什么扩容因子是1.5而不是2。这些细节全部指向同一个核心思想——用空间换时间减少拷贝次数。6.3 从数组插入看Java的排序体系——Comparator与Comparable这道题只是“在已排序数组中插入”但往深了想它的底层逻辑跟Java整个排序体系是打通的。Arrays.sort的源码里对不同的数据规模和类型会智能选择插入排序、快速排序还是归并排序。其中插入排序在小规模数据比如少于47个元素时反而比快排更快因为快排有递归开销和分区开销。也就是说你今天写的这个插入逻辑实际上是JDK排序算法在底层的组成部分之一。理解了插入排序的细节就掌握了Arrays.sort的一部分实现原理。这也是为什么这道经典题能出现在各大公司的面试题库里——它是整个排序算法知识树的地基。7. 常见问题速查与踩坑实录7.1 问题速查表症状可能原因解决方案ArrayIndexOutOfBoundsException新数组长度没加1或arraycopy的长度参数算错检查new int[arr.length 1]第二段拷贝长度应为arr.length - insertPos插入到大数后面结果错误insertPos初始值写成了0导致找不到插入位置时默认插到开头初始值必须设为arr.length降序数组插入结果乱序比较逻辑用的是升序条件增加升降序判断降序用插入值等于已有值时位置不稳定和两种写法结果不同根据需求明确用插前面用插后面二分版本在某些数据上死循环终止条件和边界收缩写错用左闭右开模板while (left right)right mid而不是mid - 1原数组为null时NPE没有判空方法开头加if (arr null)返回新数组7.2 数组中插入操作最常见的两个崩溃现场崩溃现场一扩容忘加1。新手最容易犯的错是创建新数组时写new int[arr.length]然后插入后才发现少了一个位置。这个错误通过异常信息很容易定位真正麻烦的是insertPos算错——不报异常但结果悄悄变错。崩溃现场二忘记考虑降序。因为大部分教材默认数组是升序很多人在写代码时把逻辑写死。等到测试用例换成降序数组才发现全军覆没。我的建议是写方法之前,先确认两个问题——原数组是否一定升序是否允许重复值把这两个条件说清楚再动手写代码。经验丰富的开发者都会有这个习惯动手前先把输入约束问明白。7.3 我给初学者的三个建议这道题我不是第一次讲了每次带新人或者帮读者看代码我都会强调三个点第一必须手写一遍不用任何工具类的版本。什么Arrays.sort、System.arraycopy都不用纯自己写for循环挪元素。这个过程虽然笨拙但能帮你真正理解数组的内存布局和下标运算。跳过这一步直接背API遇到问题还是会懵。第二写完之后一定要用空数组、单元素数组、全重复数组去测。这三个用例能暴露90%的边界问题。我见过太多人拿一个正常的测试用例跑通了就觉得完事大吉结果换一组数据立刻崩。第三对比着看ArrayList.add的源码。这个题目是理解ArrayList的最佳敲门砖。ArrayList的插入逻辑本质上就是“先扩容再移动最后赋值”只不过它把容量管理做成了自动化的。把这道题吃透再去看ArrayList源码你会觉得非常轻松。这也是我觉得这道题最大的学习价值——花半小时弄清一个基础操作后面看源码、学集合框架都能少走很多弯路。