自定义排序实现数组平方排序出错，请求排查（禁用Array.sort()）

核心错误点 #

• 重复平方导致数值溢出与数据破坏：
  你的双重循环里，每次内层迭代都会重新计算arr[i]和arr[j]的平方。比如处理初始值为-4的arr[0]时，第一次j=1时arr[0]被转为16；当j=2时，又会把已经平方后的16再平方成256，后续j=3、4时还会继续重复平方操作，最终导致数值溢出（出现43046721、1874919424这类溢出后的错误值），同时原始数据被彻底破坏，无法得到正确的平方结果。
• 排序逻辑的错误应用：
  即使忽略重复平方的问题，当前的排序逻辑也存在问题——冒泡排序的核心是相邻元素比较交换，但你这里的双重循环是将arr[i]和所有arr[j]（j>i）比较交换，且每次比较前都修改了arr[i]和arr[j]的值，导致后续比较的基础已经错误。

修正后的代码 #

正确的思路是先统一计算所有元素的平方，再进行排序，或者利用原数组有序的特性用更高效的双指针法实现。以下是两种可行方案：

方案1：先平方再用冒泡排序 #

class Solution {
    public int[] sortedSquares(int[] arr) {
        // 第一步：统一计算所有元素的平方
        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr[i] * arr[i];
        }
        // 第二步：冒泡排序实现升序排列
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr;
    }
}

方案2：双指针法（针对有序数组的高效实现） #

原数组是非递减排序的，平方后的数组最大值必然出现在两端。可以用双指针从两端向中间遍历，将较大的平方值放到结果数组的末尾，时间复杂度为O(n)：

class Solution {
    public int[] sortedSquares(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        int left = 0;
        int right = n - 1;
        int index = n - 1;
        
        while (left <= right) {
            int leftSquare = arr[left] * arr[left];
            int rightSquare = arr[right] * arr[right];
            
            if (leftSquare > rightSquare) {
                result[index] = leftSquare;
                left++;
            } else {
                result[index] = rightSquare;
                right--;
            }
            index--;
        }
        return result;
    }
}

测试验证 #

输入[-4,-1,0,3,10]时，两种方案都能输出正确结果[0,1,9,16,100]。

内容的提问来源于stack exchange，提问作者Jeevan Jitu