##题目描述
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
##解题思路
1,暴力遍历法,取出所有奇数放到一个数组里,取出所有偶数放到一个数组里,然后把所有奇数和偶数先后放入原数组
2,插入法,时间复杂度也是o(n^2)但是不需要开辟额外空间
##代码实现
package 数组; /** * * 输入一个整数数组,实现一个函数来调整该数组中数字的顺序 使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分 * 并保证奇数和奇数,偶数和偶数之间的相对位置不变。 */ public class ReOrderArray { public static void main(String[] args) { int[] array = { 1, 2, 3, 4, 5 }; new ReOrderArray().reOrderArray(array); } // ===============================================================暴力遍历法空间占用o(n),时间占用o(n^2) public void reOrderArray(int[] array) { if (array == null || array.length < 1) { return; } int size = array.length; int sinlen = 0; for (int i = 0; i < size; i++) { if (array[i] % 2 == 1) { sinlen++; } } int doulen = size - sinlen; // System.out.println(doulen); int[] sinArray = new int[sinlen]; int[] douArray = new int[doulen]; int j = 0; int k = 0; for (int i = 0; i < size; i++) { if (array[i] % 2 == 0) { douArray[j++] = array[i]; } if (array[i] % 2 == 1) { sinArray[k++] = array[i]; } } for (int i = 0; i < sinlen; i++) { array[i] = sinArray[i]; System.out.print(sinArray[i]); } System.out.println(); for (int i = 0; i < doulen; i++) { array[sinlen + i] = douArray[i]; System.out.print(douArray[i]); } System.out.println(); for (int i = 0; i < size; i++) { System.out.print(array[i]); } } // ==============================================================优化解法 /** * 1.要想保证原有次序,则只能顺次移动或相邻交换。 2.i从左向右遍历,找到第一个偶数。 3.j从i+1开始向后找,直到找到第一个奇数。 * 4.将[i,...,j-1]的元素整体后移一位,最后将找到的奇数放入i位置,然后i++。 5.終止條件:j向後遍歷查找失敗。 */ public void reOrderArraySuper(int[] array) { if (array == null || array.length < 1) { return; } int i = 0; int j = 0; while (i < array.length) { while (i < array.length && isSingle(array[i])) i++; j = i+1; //第一个偶数的位置 while(j<array.length&&!isSingle(array[j])) j++; //j从i+1开始向后找,直到找到第一个奇数。 if(j<array.length){ int temp = array[j]; //当前j的位置在i之后的第一个奇数 for (int k = j-1; k >=i; k--) { array[k+1] = array[k]; //向后移动位置 } array[i] = temp; i++; }else{ break; } } } // 用于判断是否为奇数的函数 public boolean isSingle(int num) { if (num % 2 == 1) return true; else return false; } }