排序应用(一)

时间最少，辅助空间最少，把所有奇数移动到偶数前边

思想：从顺序表的两边同时遍历进行奇偶交换

void move1(){
    int A[6]={4,5,1,2,6,3};
    int temp;
    int i=0,j=5;
    while(i<j){
        while(A[i]%2==1){i++;}
        while(A[j]%2==0){j--;}
        if(i<j){
            temp=A[i];
            A[i]=A[j];
            A[j]=temp;
        }
        i++;
        j--;
    }
    for(int i=0;i<6;i++){
        printf("%d ",A[i]);
    }
    printf("\n");
}

找出第k个小的元素

int k_elem(int A[],int low,int high,int k){
    int pivot=A[low];
    int low_temp=low;
    int high_temp=high;
    while(low<high){
        while(low<high&&A[high]>=pivot){high--;}
        A[low]=A[high];
        while(low<high&&A[low]<=pivot){low++;}
        A[high]=A[low];
    }
    A[low]=pivot;
    if(low==k){return A[low];}
    else if(low<k){return k_elem(A,low+1,high_temp,k);}
    else {return k_elem(A,low_temp,low-1,k);}
}