3.5 题解-调整数组顺序使奇数在做偶数在右

2019-03-23  本文已影响0人  Aurochsy

Chapter3: 更好的查找与排序算法

5. 题解:调整数组顺序使奇数在左偶数在右

题目

输入一个整数数组,调整数组中数字的顺序,使得所有奇数为域数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为O(n)

上一节提到了在解题时想出算法的方法论,这里用到的就是模式匹配法,用快速排序和归并排序的思想

用快速排序的思想

基本思想

代码

//用快速排序-双向扫描分区法的思想 
void sortOddandEven(int* arr,int begin,int end){
    int left=begin;
    int right=end;
    while(left<=right){
        while((arr[left]&1)==1){//如果是奇数其末尾为1,与1相与结果为1
            left++;
        }
        while((arr[right]&1)==0){
            right--;
        }
        /*当left和right停止移动时交换arr[left]进而aar[right]*/ 
        if(left<right){//最后遍历完全部元素时,left和right交错,此时不应该进行交换了 
            int tmp=arr[left];
            arr[left]=arr[right];
            arr[right]=tmp;
        }
    }
}

用归并排序的思想

基本思想

代码

//归并分区的思想 
void sortOddandEven3(int* arr,int begin,int end){
    
    int arrLen=end-begin+1;
    int tmpArr[arrLen];//临时数组 
    int scan=begin;//扫描指针 
    int left=begin;//左指针 
    int right=end;//右指针 

    while(left<=right){
        if(arr[scan]&1==1){//arr[scan]是奇数 
            tmpArr[left]=arr[scan];//交换arr[scan]与arr[left]的值,即将奇数放在数组左边 
            left++;
            scan++;
        }
        else{//arr[scan]是偶数 
            tmpArr[right]=arr[scan];
            right--;
            scan++;
        }
    }
    int i=0;//临时数组当前的存取指针 
    while(begin<=end){
        arr[begin++]=tmpArr[i++];
    }
    
}
上一篇 下一篇

猜你喜欢

热点阅读