1 题目
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
2 解析
（1）方法一：使用python内置的sort的快排
空间复杂度O(n)，时间复杂度O(nlogn)
（2）方法二
直接插入排序，但是超过时间限制
时间复杂度 O ( n 2 ) O(n^2) O(n2)，时间复杂度O(1)
（3）方法三
双指针
时间复杂度O(n)，空间复杂度O(n)
3 python 实现
（1）方法一
# 快速排序 def sortedSquares(self, nums: List[int]) -> List[int]: res = [] for i in nums: res.append(i*i) # 第一种方法，使用python内置的sort方法 res.sort() # 第二种方法，自己写快排算法 self.QuckSort(res,0,len(nums)-1) return res def partition(self,arr,low,high): i = low-1 pivot =arr[high] for j in range(low,high): if arr[j]<=pivot: i+=1 arr[i],arr[j] = arr[j],arr[i] arr[i+1],arr[high] = arr[high],arr[i+1] return i+1 def QuckSort(self,arr,low,high): if low <high: p = self.partition(arr,low,high) self.QuckSort(arr,low,p-1) self.QuckSort(arr,p+1,high)
（2）方法二
# 直接插入排序;注意，超过时间限制 def sortedSquares(self, nums: List[int]) -> List[int]: if len(nums)==0: return nums nums[0] = nums[0]*nums[0] for i in range(1,len(nums)): temp = nums[i]*nums[i] j=i-1 while j>=0 and temp<nums[j]: nums[j+1] =nums[j] j -=1 nums[j+1] = temp return nums
（3）方法三
# 双指针 def sortedSquares(self, nums: List[int]) -> List[int]: if len(nums)==1: return [nums[0]*nums[0]] res = [-1]*len(nums) idx = len(nums)-1 right =len(nums)-1 left = 0 while left<=right: if nums[left]*nums[left]>nums[right]*nums[right]: res[idx] = nums[left]*nums[left] left +=1 else: res[idx] = nums[right]*nums[right] right -=1 idx -=1 return res
