給你一個按 非遞減順序 排序的整數數組 nums，返回 每個數字的平方 組成的新數組，要求也按 非遞減順序 排序。

示例 1：
輸入：nums = [-4,-1,0,3,10]
輸出：[0,1,9,16,100]
解釋：平方后，數組變為 [16,1,0,9,100]
排序后，數組變為 [0,1,9,16,100]
示例 2：
輸入：nums = [-7,-3,2,3,11]
輸出：[4,9,9,49,121]

面對這樣的題目，先把原來的數據平方后，有幾種算來進行排序

1.直接插入排序：

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {//直接插入排序int i, j;//平方后的數組for (i = 0; i < nums.size(); i++){nums[i] = nums[i] * nums[i];}int temp = nums[0];for (i = 1; i < nums.size(); i++){if (nums[i] < nums[i - 1])//小的做為哨兵{temp = nums[i];//復制為哨兵for (j = i - 1; j >= 0 && nums[j] > temp ;  j--){nums[j + 1] = nums[j];}nums[j+1] = temp;}}return nums;}
};

結果同樣的不盡如人意。

此算法的時間復雜度為O（n^2）

2.折半插入排序

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {//直接插入排序int i, j,low,high,mid;//平方后的數組for (i = 0; i < nums.size(); i++){nums[i] = nums[i] * nums[i];}int temp = nums[0];for (i = 1; i < nums.size(); i++){low=0;high=i-1;mid=(low+high)/2;if (nums[i] < nums[i - 1])//判斷是否比前一個小，如果小就插入{temp = nums[i];//復制為哨兵，進行判斷while(low<=high){if(temp>=nums[mid]){low=mid+1;}else{high=mid-1;}mid = (low + high) / 2;}for (j = i - 1; j>high ;  j--){nums[j + 1] = nums[j];}nums[high+1] = temp;}}return nums;}
};

折半插入排序插入排序也確實會比直接插入快了點。折半插入排序只是減少了比較次數，時間復雜度還是O(n^2)

3.希爾排序時間復雜度約為O（n^1.3）, 最壞情況下時O（n^2）

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int step,i,j,temp;//平方后的數組for (i = 0; i < nums.size(); i++){nums[i] = nums[i] * nums[i];}//希爾排序for(step=nums.size()/2;step>0;step/=2)//步長變化{for(i=step;i<nums.size();i++){temp=nums[i];for(j=i-step;j>=0 && temp<nums[j];j-=step){nums[j+step]=nums[j];//后移}nums[j+step]=temp;}}return nums;}
};

結果有了顯著的提升

采用空間換時間雙指針的方法，優點類似與歸并排序

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int pos,i,j;vector<int> temp(nums.size());for(i=0,j=nums.size()-1,pos=nums.size()-1;i<=j;){if(nums[i]*nums[i]>nums[j]*nums[j]){temp[pos--]=nums[i]*nums[i];i++;}else{temp[pos--]=nums[j]*nums[j];j--;}}return temp;}
};

空間復制度為O（n）

效果顯而易見

4.快速排序

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {for(int i=0;i<nums.size();i++){nums[i]=nums[i]*nums[i];}QuickSort(nums,0,nums.size()-1);return nums;}void QuickSort(vector<int>& nums,int low,int high){if(low<high){int pivotpos=Patition(nums,low,high);QuickSort(nums,low,pivotpos-1);QuickSort(nums,pivotpos+1,high);}}//快速排序int Patition(vector<int>& number,int low,int high){    int pivot=number[low];//樞紐while(low<high){   while(low<high && number[high]>=pivot) {high--;}number[low]=number[high];//置換while(low<high && number[low]<=pivot){low++;}number[high]=number[low];}number[low]=pivot;return low;}
};

5.歸并排序

#include <iostream>
#include<vector>using namespace std;
//歸并排序void Merge(vector<int>& nums,int low,int mid,int high)
{int* temp = (int*)malloc(nums.size());int count, i, j;for (count = low; count <=high; count++){temp[count] = nums[count];}for (i = low, j = mid + 1, count = i; i <= mid&&j <= high; count++){if (temp[i] <= temp[j]){nums[count] = temp[i++];}else{nums[count] = temp[j++];}}while (i <= mid){nums[count++] = temp[i++];}while (j <= high){nums[count++] = temp[j++];}}void MergeSort(vector<int>& nums, int low, int high)
{if (low < high){int	mid = (low + high) / 2;MergeSort(nums, low, mid);MergeSort(nums, mid + 1, high);Merge(nums, low, mid, high);}}int main()
{//nums = [-4, -1, 0, 3, 10]vector<int> nums = { 16,1,0,100,10 };MergeSort(nums, 0, 4);for (int i = 0; i < 5; i++){printf(" % d\t", nums[i]);}}

leetcode中超時了，但是自己測試了一下沒啥問題

6.堆排序

void HeadAdjust(vector<int>& nums, int k, int len)
{int i, j;nums[0] = nums[k];for (i = 2 * k; i <= len; i*=2){if (i < len-1 && nums[i] < nums[i + 1]){i++;}if (nums[0] >= nums[i]){break;}else{nums[k] = nums[i];k = i;}}nums[k] = nums[0];
}
//大根堆
void BuildMaxHeap(vector<int>& nums,int len)
{int i = 0;for ( i= len / 2; i > 0; i--){HeadAdjust(nums, i, len);}
}void HeapSort(vector<int>& nums, int len)
{int i,temp=0;BuildMaxHeap(nums, len);//初始化大根堆for ( i= len-1; i > 1; i--){temp = nums[i];nums[i] = nums[1];nums[1] = temp;HeadAdjust(nums, 1, i - 1);}}int main()
{//nums = [-4, -1, 0, 3, 10]vector<int> nums = { 0,53,17,78,9,45,65,87,32 };HeapSort(nums,nums.size());//MergeSort(nums, 0, 7);for (int i = 1; i < 9; i++){printf(" %d\t", nums[i]);}}