有序数组排序

题目描述

day01题目.png

算法题解

思路1——双指针法
按照题目[额外要求]可以排除[暴力解法]，分析题目条件可得数组是有序的(即递增)，且题目示例中包含正数和负数,所以平方后数组中的最大值就在数组的[两端]，即左边或者右边，不可能是中间，既然有双端的操作，我们可以尝试双指针法，具体流程如下：
1.定义两个指针i和j分别指向nums数组的起始和终止位置。
2.定义一个和nums 等长的[辅助数组] result綻义指针k指向result数组终止位置。
3.如果nums[i] * nums[i] < nums[j] * nums[j] 那么result[k--] = nums[j] * nums[j]。
4.如果nums[i] * nums[i] > nums[j] * nums[j] 那么result[k--] = nums[i] * nums[i]。

上机代码

#include <stdio.h>
#include <math.h>
int main(){
    int nums[]={-4,-1,0,3,10};
    int length=sizeof(nums)/sizeof(nums[0]);//记录数组长度 
    int result[length];//记录数组元素平方后进行排序后的结果 
    int k=length-1;
    int a=0,b=length-1;
    int c,d;
    while(a<=b){
        if(pow(nums[a],2)<pow(nums[b],2)){
            result[k--]=pow(nums[b--],2);
        }
        else{
            result[k--]=pow(nums[a++],2);
        }  
    }
    for(int i=0;i<length;i++){
        printf("%d\n",result[i]);
    } 
    return 0;
} 

运行结果

day01运行.png