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