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

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

思路及实现： 解法一： 类似于冒泡排序， 从后往前，当前偶后奇时交换，每一趟可以排好首元素

*时间复杂度O (n^2)，空间复杂度O (n)

class Solution { public: void reOrderArray(vector<int> &array) { for (int i = 0; i < array.size()/2;i++) { for (int j = array.size() - 1; j>i;j--) { if (array[j - 1]%2 == 0 && array[j] % 2 == 1 ) { swap(array[j], array[j-1]); } } } } };

解法二： 类似于插入排序 1.从左向右遍历，[ i ] 找奇数，temp保存奇数的值， 2.将[ i ] 前面的（上一个奇数之后的）所有偶数整体后移一位， 3.并将保存的奇数值存入整体后移的第一个偶数中（下标最小）， 4.直至[ i ] 查找不到奇数

*时间复杂度O (n^2)，空间复杂度O (n)

public class Solution { public void reOrderArray(int [] array) { for(int i=1; i<array.length; i++){ if(array[i]%2 == 1){ int j=i-1; int temp=array[i]; //暂存奇数值 while(j>=0 && array[j]%2 ==0){ array[j+1]=array[j]; //将奇数前的偶数整体后移 j--; } array[j+1]=temp; } } } }

解法三：空间换时间

import java.util.ArrayList; import java.util.List; public class Solution { public void reOrderArray(int [] array) { List<Integer>ls1=new ArrayList<Integer>(); List<Integer>ls2=new ArrayList<Integer>(); for(int i=0;i<array.length;i++){ if(array[i]%2==1){ //奇数存入ls1 ls1.add(array[i]); } else { //偶数存入ls2 ls2.add(array[i]); } } int i=0; for(int j = 0;j<ls1.size();j++){ //将奇数存回array array[i]=ls1.get(j); i++; } for(int k = 0;k<ls2.size();k++){ //将偶数存回array array[i]=ls2.get(k); i++; } } }