【Java 实现经典算法】四：调整数组顺序使奇数位于偶数前面
题目来自剑指Offer之十四。
基本解法
- 保证奇数和奇数，偶数和偶数之间的相对位置不变
- 遍历每个元素，一旦发现偶数就取出来，让它之后的元素向前移动，把取出来的元素补到最后的空位上
- 类似插入排序，具体实现是外循环找奇数，内循环将该数之前的偶数移位
public static void reOrderArray(int array[]){
if(array == null || array.length == 0){
return;
}
for(int i = 1; i < array.length; i++){
int current = array[i];
if(!isEven(current)){ //找到奇数位置
int j = i - 1; //从奇数前一个位置开始
for(; j >= 0 && isEven(array[j]); j--){ //发现偶数就移位
array[j + 1] = array[j];
}
array[j + 1] = current; //把奇数插入到偶数前面
}
}
}
高效解法
- 相对位置可以改变时，更为高效的解法
- 维护两个指针，一首一尾
- 首指针向后遍历，检测到偶数时暂停，尾指针向前遍历，检测到奇数时暂停
- 交换首尾两个数
- 继续这样的判断，直到首尾指针相遇。
public static void reOrderArray2(int array[]){
int low = 0;
int high = array.length - 1;
while(low < high){
while(low < high && !isEven(array[low])){
low++;
}
while(low < high && isEven(array[high])){
high--;
}
if(low < high){
int temp = array[low];
array[low] = array[high];
array[high] = temp;
}
}
}
判断一个数是否为偶数
public static boolean isEven(int i){
return (i & 0x1) == 0;
}
我组建了一个技术交流群，提供免费的每日科技早报服务，里边也会有众多知名互联网企业的技术大佬一起交流学习，共同成长。需要的朋友可以加我微信（微信ID：919201148），我拉你进群，并有福利相送。
关注我的微信公众号，回复“礼包”领取我的学习资料
涵盖自学编程、Java技术、分布式笔记、算法刷题和程序员必读电子书等众多资料合集。
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
