题目描述：
给定一个按非递减顺序排序的整数数组 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 已按非递减顺序排序。

思路：
先将原数组平方，再通过快速排序法排序。快速排序详见我的第一篇文章“基础训练1：数列排序”。
代码：（C++）

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int i;
        for(i=0;i<A.size();i++)
        {
            A[i]=A[i]*A[i];
        }
        quick_sort2(A,0,A.size()-1);
        return A;
    }
    void quick_sort2(vector<int>& A,int l,int r)
    {
         if (l<r)
    {
        int i = l, j = r, x = A[i];
        while (i < j)
        {
            while(i < j && A[j] >= x) // 从右向左找第一个小于x的数
                j--;  
            if(i < j) 
                A[i++] = A[j];
            
            while(i < j && A[i] < x) // 从左向右找第一个大于等于x的数
                i++;  
            if(i < j) 
                A[j--] = A[i];
        }
        A[i] = x;
        quick_sort2(A, l, i - 1); // 递归调用 
        quick_sort2(A, i + 1, r);
    }
    }
};

提交结果：

提交结果.png

补充：
C++自带内置函数std::sort()，可以进行快速排序

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int i;
        for(i=0;i<A.size();i++)
        {
            A[i]=A[i]*A[i];
        }
        std::sort(A.begin(),A.end());
        return A;
    }
};

提交结果2.png