【剑指 offer】调整数组顺序使奇数位于偶数前面

✨个人主页：bit me👇
✨当前专栏：算法训练营👇

描述：

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

思路：

• 有两种实现方式，第一种是遍历原数组，用两个数组分别存储奇数和偶数，注意顺序不改变，然后进行合并，奇数数组在前，偶数数组在后。第二种方法是遍历数组，遇到奇数就存储，偶数就跳过，但是记得在偶数前面留个空位置，方便插入奇数元素，遍历完成就代表结果出来了。

方法一：俩数组分别存储奇数偶数，然后进行合并。

public class Solution {public void reOrderArray(int [] array) {ArrayList<Integer> list1 = new ArrayList<>();ArrayList<Integer> list2 = new ArrayList<>();for(int num:array){if(num % 2 == 0){list2.add(num);}else{list1.add(num);}}for(int i = 0;i < list1.size();i++){array[i]=list1.get(i);}for(int i = 0;i < list2.size();i++){array[i+list1.size()]=list2.get(i);}}
}

方法二：遍历奇数，合并剩下的偶数，自然就完成了

1. 判断特殊情况，数组为空或者长度为 0 。

if(array == null || array.length == 0){return;
}

2. 遍历循环，判断奇数，然后把奇数存储起来，最终让偶数整体往后移一步

int k = 0;
for(int i = 0; i < array.length; i++){if((array[i] & 1) == 1){int temp = array[i];int j = i;while(j > k){array[j] = array[j - 1];j--;}array[k++] = temp;}
}

• 在这里面需要注意的是，边界判断：当数组第一个位置为偶数，第一次循环开始，k=0，执行到最后j=1，把0位置的偶数后挪正好
• k++，先执行再 + 1，保证了奇数能按顺序来进行排列

public class Solution {public void reOrderArray(int [] array) {if(array == null || array.length == 0){return;}int k = 0;for(int i = 0; i < array.length; i++){if((array[i] & 1) == 1){int temp = array[i];int j = i;while(j > k){array[j] = array[j - 1];j--;}array[k++] = temp;}}}
}