Chapter3: 更好的查找与排序算法
5. 题解：调整数组顺序使奇数在左偶数在右
题目
输入一个整数数组，调整数组中数字的顺序，使得所有奇数为域数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)
上一节提到了在解题时想出算法的方法论，这里用到的就是模式匹配法，用快速排序和归并排序的思想
用快速排序的思想
基本思想
- 设置两个指针
left和right,left初始化为数组第一个元素的位置，right初始化为数组最后一个元素的位置 -
left从左往右扫，遇到奇数就移向下一位(left++)，遇到偶数就暂停不动；right从右往左扫，遇到偶数就移向上一位(right--),遇到奇数就暂停不懂。 - 如果
left和right都不动了，就交换它们对应的值，并接着往下移动。
代码
//用快速排序-双向扫描分区法的思想
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;
}
}
}
用归并排序的思想
基本思想
- 设置一个辅助数组
tmpArr，大小等于原数组 - 设置一个扫描指针，从左往右扫描，如果遇到奇数就放在
tmpArr的左边，遇到偶数就放在tmpArr的右边，具体实现就是设置left和right指针，这两个指针初始化分别在第一个元素和最后一个元素，放一个数对应的指针挪一位，left往右，right往左。
代码
//归并分区的思想
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++];
}
}
