每日一题之《剑指offer》13题: 调整数组顺序使奇数位于偶数前面
未经允许，不得转载
调整数组顺序使奇数位于偶数的前面
难易度：⭐⭐
输入一个整数数组，实现一个函数来调整该数组中数字的顺序
使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分
并保证奇数和奇数，偶数和偶数之间的相对位置不变，即：要求具有稳定性
例如：对于数组[1,2,3,4,5,6,7]进行调整后的数组为：[1,3,5,7,2,4,6]
第一眼看到本题时，我头脑中闪过最简单的思路是这样的：
准备两个队列，遍历数组的同时，奇数放入奇数队列中，偶数放入偶数队列，然后将奇数队列和偶数队列依次出队的同时赋值给原数组
代码如下：
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
public static void reOrderArray(int[] array) {
Queue<Integer> evenQueue = new LinkedList<>();
Queue<Integer> oddQueue = new LinkedList<>();
for (int i = 0; i < array.length; i++) {
if ((array[i] & 1) == 0) {
evenQueue.offer(array[i]);
} else {
oddQueue.offer(array[i]);
}
}
int i = 0;
while (!oddQueue.isEmpty()) {
array[i] = oddQueue.poll();
i++;
}
while (!evenQueue.isEmpty()) {
array[i] = evenQueue.poll();
i++;
}
}
}
但是这种写法除了要使用额外的空间，还要遍历两次数组的长度。不妨换一个角度想，能否不适用额外的空间完成这样的一件事呢，调整奇偶的顺序和排序的思想实际上是等同的，所以我们就有了：
"插入排序"的思路:
依次遍历数组，使用一个变量去记录偶数的长度，如果遍历到偶数那么仅仅让表示偶数长度的变量加一即可，如果遍历到奇数，那么就依次与前一个数字置换位置直到奇数跑到所有的偶数前为止，因为本思路的思想就是插入排序的思想，而插入排序是一个具有稳定性的排序，所以本思路正确，如果不知道什么是稳定性，可以看我的文章 排序算法稳定性及桶排序。
本思路的代码如下：
public class Solution {
public static void reOrderArray(int[] array) {
int evenLen = 0;
for (int i = 0; i < array.length; i++) {
if ((array[i] & 1) == 0) {
evenLen++;
} else {
for (int j = i; j > i - evenLen; j--) {
swap(array, j, j - 1);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}
当然，对于排序而言，最好的自然是时间复杂度为O(NlgN)级别的排序，我们熟知的有两种，归并与快排，对于快排而言partition的过程无法保证稳定性，而归并排序是一种可以保证稳定性的算法，不过与此同时，也多出了额外的使用空间，使用归并排序的思想写出的代码如下：
public class Solution {
public static void reOrderArray(int[] array) {
if (array == null || array.length <= 1) {
return;
}
mergeSort(array, 0, array.length - 1);
}
public static void mergeSort(int[] arr, int l, int r) {
if (l < r) {
int mid = l + ((r - l) >> 1);
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
oddEvenMerge(arr, l, mid, r);
}
}
public static void oddEvenMerge(int[] arr, int l, int mid, int r) {
int p1 = l;
int p2 = mid + 1;
int[] help = new int[r - l + 1];
int i = 0;
while (p1 <= mid && (arr[p1] & 1) != 0) {
help[i++] = arr[p1++];
}
while (p2 <= r && (arr[p2] & 1) != 0) {
help[i++] = arr[p2++];
}
while (p1 <= mid) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (int j = 0; j < help.length; j++) {
arr[l + j] = help[j];
}
}
}
归并排序的思路，其实也很简单
如果不了解归并排序的话，可以看我的文章时间复杂度的认识,递归,归并排序。
但是至此，我列举的几种方法其实均不是最优解，最优解的思路为 01 statble sort,在C艹 STL库中，具有一个方法 stable_sort ，这个方法既可以快速进行排序又能够保持排序算法的稳定性，不过因为我能力有限，实在没有搞懂本算法。如果可以写出插入排序或者归并排序的思路，说明为什么不可以用快速排序的思路解决本题（因为快排不具有稳定性）那么本题也可以给一个及格分数。
不过这个问题还没有完，因为在牛客网的题库中本题需要写出具有稳定性的算法，但是《剑指offer》第二版的原题是这样的：
输入一个整数数组，实现一个函数来调整该数组中的数字的顺序
使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分
原题并未要求结果为具有稳定性的。我们就可以借用快排的partition思想，在数组的前面设置一个指针标记偶数，数组的末尾设置一个指针标记奇数
指向偶数的 evenP 一直向后移动至偶数的位置上，指向奇数的 oddP 则一直向前移动至指向奇数为止，当移动好之后，两者指向的数字发生交换行为：
直至 evenP >= oddP
代码如下：
public class Solution {
public static void reOrderArray(int[] array){
if(array == null || array.length <= 1){
return;
}
int evenP = 0;
int oddP = array.length - 1;
while(evenP < oddP){
while(evenP < oddP && !isEven(array[evenP])){
evenP++;
}
while(evenP < oddP && isEven(array[oddP])){
oddP--;
}
if(evenP < oddP){
swap(array,evenP,oddP);
}
}
}
public static boolean isEven(int num){
return (num & 1) == 0;
}
public static void swap(int[] arr,int i,int j){
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}
投递大疆等公司6个岗位 >