LeetCode977有序数组的平方

思路①：先平方，后快排，输出（基准元素，左小右大）
时间复杂度：O（nlogn）
思路②：双指针左右开弓，首先原数组已经是按照非递减顺序排序，那么最大值只有可能出现在最右边或者最左边，那么我们可以创建一个与原数组等长的空数组，双指针，i指向原数组的最左边，j指向最右边，每次循环都判断是左边大还是右边大，将大的值放入空数组中（空数组的指针k从末尾往前跳，最末尾是最大的值）

/*** Note: The returned array must be malloced, assume caller calls free().*/
int* sortedSquares(int* nums, int numsSize, int* returnSize) {int *output=(int*)malloc(sizeof(int) * numsSize);int k=numsSize-1;int i=0,j=numsSize-1;while(i<=j){if(nums[i]*nums[i]<nums[j]*nums[j]){output[k--]=nums[j]*nums[j];//谁大放谁j--;}else{output[k--]=nums[i]*nums[i];i++;}}*returnSize = numsSize;//设置返回数组的大小return output;
}