学习---3

有序数组的排序：

一、暴力解法：

思路：遍历数组，对每个数组元素进行平方，再用sort排序。

时间复杂度：O(nlog n)

二、双指针解法：

思路：如果有序数组中有负数，那么这个负数平方之后就有可能比正数的平方大，所以平方后最大的元素一定再数组的两边，而不是中间。所以用两个指针，一个指向第一个元素，一个指向最后一个元素，比较这两个指针所指的元素平方后哪个更大，再用一个数组来存放更大的数，然后指针移动。

代码实现：

int arr[6]={-3,-2,-1,0,1,2}; int res[6]={0}; //用于存放比较好后的元素 int k=sizeof(arr)/sizeof(arr[0])-1; //记录存放res数组的位置 for(int i=0,j=sizeof(arr)/sizeof(arr[0])-1;i<=j;){ if（arr[i]*arr[i]>arr[j]*arr[j]){ res[k--]=arr[i]*arr[i]; i++; }else{ res[k--]=arr[j]*arr[j]; j--; } } //返回res数组

时间复杂度为O(N);

(本文章是本人学完后进行整理，加入了自己的理解，仅供参考，有不正确的地方欢迎指出！)