有序数组的平方

给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例 1：

输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]

示例 2：

输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非递减顺序排序。

class Solution {
    public int[] sortedSquares(int[] A) {
        int[] A2 = new int[A.length];
        for (int i = 0; i < A.length; i++) {
            A2[i] = A[i] * A[i];
        }
        sort(A2, 0, A2.length - 1);
        return A2;
    }

//快速排序
    private void sort(int[] array, int _left, int _right) {
        int left = _left;
        int right = _right;
        int temp = 0;
        if (left <= right) {
            temp = array[left];
            while (left != right) {
                while (left < right && array[right] >= temp) {
                    right--;
                }
                array[left] = array[right];

                while (left < right && array[left] <= temp) {
                    left++;
                }
                array[right] = array[left];
            }
            array[left] = temp;
            sort(array, _left, left - 1);
            sort(array, right + 1, _right);
        }

    }
}