필기시험 문제 의 상대 적 위치 가 변 하지 않 는 양수 정렬

3663 단어
필기시험 문제: 하나의 정형 배열 에 약간의 양수 와 음수 가 존재 한다 고 가정 하고 현재 특정한 알고리즘 을 통 해 이 배열 의 모든 음 수 를 양수 의 왼쪽 에 있 게 하고 음수 부품 과 양수 간 요소 의 상대 적 인 위치 가 변 하지 않도록 확보한다.시공 복잡 도 요 구 는 각각 o (n), o (1) 이다.
예컨대  -3, 4, 2. - 1, 7, 3. - 5 정렬 후. - 3. - 1. - 5, 4, 2, 7, 3.
/ * 1.0 버 전 사상 * /
복잡 도 를 고려 하여 나의 실현 방법 은 첫 번 째 potive 를 찾 고 첫 번 째 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){
        if(a[i]<0){
            temp=i-1;
            while(temp>=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(p0);//find first negative after first postive
        
        if(ppos_fir;i--){
                temp=a[i];
                a[i]=a[i-1];
                a[i-1]=temp;
            }
            p=pos_fir++; 
        }        
    }*/
    for(i=0;i)
        printf("%d ",a[i]);
    
    
}

 
 
다음으로 전송:https://www.cnblogs.com/johnleo/p/neg_pos_sort.html

좋은 웹페이지 즐겨찾기