笔试题相对位置不变的正负数排序-白红宇

笔试题相对位置不变的正负数排序

阅读量：6368 次

发布时间：2019-06-23

本文共 1142 字，大约阅读时间需要 3 分钟。

笔试题目：假设一整型数组存在若干正数和负数，现在通过某种算法使得该数组的所有负数在正数的左边，

且保证负数件和正数间元素相对位置不变。时空复杂度要求分别为：o(n),o(1)。

例如

-3 4 2 -1 7 3 -5

排序后

-3 -1 -5 4 2 7 3

　　/*1.0版本思想*/

　　考虑复杂度，我的实现方法是找到第一个postive，再找到第一个negative after the postive，然后进行类似一趟冒泡的排序，重复做下去，直到cann't find negative after the first postive.

　　2.0版本是对1.0版的优化

#include
     
      void swap(int *a,int *b){    int temp=*a;    *a=*b;    *b=temp;}int main(){    int a[7]={        -3,4,2,-1,7,3,-5    };    /*2.0版本*/    int length=sizeof(a)/sizeof(int);    int i,temp;    for(i=0;i
      
       =0 && a[temp]>0){                swap(&a[temp+1],&a[temp]);                temp--;            }        }    }    /*1.0版本 写的有点笨重*/     /*    int pos_fir=-1,p,i;    int n=sizeof(a)/sizeof(int);    int temp;        while(a[++pos_fir]<=0);//找到第一个正数位置     p=pos_fir;        while(p
       
        0);//find first negative after first postive                if(p
        
         pos_fir;i--){                temp=a[i];                a[i]=a[i-1];                a[i-1]=temp;            }            p=pos_fir++;         }            }*/    for(i=0;i