企业官网建设流程全解析

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, Comparator<User> 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个拷到目标数组第insertPos+1个，拷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 问题速查表

7.2 数组中插入操作最常见的两个崩溃现场

崩溃现场一：扩容忘加1。新手最容易犯的错是创建新数组时写new int[arr.length]，然后插入后才发现少了一个位置。这个错误通过异常信息很容易定位，真正麻烦的是insertPos算错——不报异常，但结果悄悄变错。

崩溃现场二：忘记考虑降序。因为大部分教材默认数组是升序，很多人在写代码时把逻辑写死。等到测试用例换成降序数组才发现全军覆没。我的建议是：写方法之前,先确认两个问题——原数组是否一定升序？是否允许重复值？把这两个条件说清楚，再动手写代码。经验丰富的开发者都会有这个习惯：动手前先把输入约束问明白。

7.3 我给初学者的三个建议

这道题我不是第一次讲了，每次带新人或者帮读者看代码，我都会强调三个点：

第一，必须手写一遍不用任何工具类的版本。什么Arrays.sort、System.arraycopy都不用，纯自己写for循环挪元素。这个过程虽然笨拙，但能帮你真正理解数组的内存布局和下标运算。跳过这一步直接背API，遇到问题还是会懵。

第二，写完之后一定要用空数组、单元素数组、全重复数组去测。这三个用例能暴露90%的边界问题。我见过太多人拿一个正常的测试用例跑通了就觉得完事大吉，结果换一组数据立刻崩。

第三，对比着看ArrayList.add的源码。这个题目是理解ArrayList的最佳敲门砖。ArrayList的插入逻辑本质上就是“先扩容，再移动，最后赋值”，只不过它把容量管理做成了自动化的。把这道题吃透，再去看ArrayList源码，你会觉得非常轻松。这也是我觉得这道题最大的学习价值——花半小时弄清一个基础操作，后面看源码、学集合框架都能少走很多弯路。