整数数组的奇数位于数组的前半部分，偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变

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

思路1：
类似于冒泡排序，从头开始，相邻元素只要是前偶后奇就交换，不同的是内循环每次都从头开始，防止一开始就有许多连续的偶数情况。

// 类似于冒泡排序，从头开始，相邻元素只要是前偶后奇就交换，不同的是内循环每次都从头开始，防止一开始就有许多连续的偶数情况public static void reOrderArray1(int[] array){int length = array.length;for (int i = 0; i < length; i++) {for (int j = 0; j < length-1; j++) {if(array[j] % 2 == 0 && array[j+1] % 2 ==1){int temp = array[j];array[j] = array[j+1];array[j+1] = temp;}}}}

思路2：
开辟一个与原数组一样大的vector,从头遍历一遍将奇数放在前面，然后再遍历一遍，将偶数接着放在后面。

public static int[] reOrderArray2(int[] array){int length = array.length;int[] newArray = new int[array.length];int j = 0;// 先存奇数for (int i = 0; i < length; i++) {if(array[i] % 2 == 1){newArray[j] = array[i];j++;}}// 再存偶数for (int i = 0; i < length; i++) {if(array[i] % 2 == 0){newArray[j] = array[i];j++;}}return newArray;}

思路3：
先计算出奇数的个数count，然后用双指针来遍历，一个从头遍历到count，一个从数组尾部遍历到count。

从前向后找到一个偶数的下标，从后向前找到一个奇数的下标，然后交换对应的值。直到遍历完整个数组。时间复杂度为O（n），空间复杂度为O（1）

// 先计算出奇数的个数count，然后用双指针来遍历，一个从头遍历到count，一个从数组尾部遍历到count。// 从前向后找到一个偶数的下标，从后向前找到一个奇数的下标，然后交换对应的值。// 直到遍历完整个数组。时间复杂度为O（n），空间复杂度为O（1）private static int[] reOrderArray3(int[] arr) {// 头部指针int front =0;// 尾部指针int end = arr.length-1;while(front < end){while (front < arr.length && arr[front] % 2 == 1){// 从前向后找偶数，如果找到(即arr[front] % 2 == 0)，则front位置不移动front ++;}while (end > 0 && arr[end] % 2 == 0){// 从后往前找奇数，如果找到(即arr[end] % 2 == 1)，则end位置不移动end --;}if (front < end){// 将前面的偶数与后面奇数交换位置int temp = arr[front];arr[front] = arr[end];arr[end] = temp;}}return arr;}

整体代码

import java.util.Scanner;public class Test9 {// 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，// 并保证奇数和奇数，偶数和偶数之间的相对位置不变。public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 英文逗号分割数字比如 3,2,1,5,6,4String temp1 = sc.nextLine();String[] s = temp1.split(",");int[] array = new int[s.length];for (int i = 0; i < s.length; i++) {array[i] = Integer.parseInt(s[i]);}/*reOrderArray1(array);for (int i = 0; i <array.length ; i++) {System.out.print(array[i]+" ");}*//*int[] finalArray = reOrderArray2(array);for (int i = 0; i <finalArray.length ; i++) {System.out.print(finalArray[i]+" ");}*/int[] finalArray = reOrderArray3(array);for (int i = 0; i <finalArray.length ; i++) {System.out.print(finalArray[i]+" ");}}// 类似于冒泡排序，从头开始，相邻元素只要是前偶后奇就交换，不同的是内循环每次都从头开始，防止一开始就有许多连续的偶数情况public static void reOrderArray1(int[] array){int length = array.length;for (int i = 0; i < length; i++) {for (int j = 0; j < length-1; j++) {if(array[j] % 2 == 0 && array[j+1] % 2 ==1){int temp = array[j];array[j] = array[j+1];array[j+1] = temp;}}}}// 开辟一个与原数组一样大的vector,从头遍历一遍将奇数放在前面，然后再遍历一遍，将偶数接着放在后面public static int[] reOrderArray2(int[] array){int length = array.length;int[] newArray = new int[array.length];int j = 0;// 先存奇数for (int i = 0; i < length; i++) {if(array[i] % 2 == 1){newArray[j] = array[i];j++;}}// 再存偶数for (int i = 0; i < length; i++) {if(array[i] % 2 == 0){newArray[j] = array[i];j++;}}return newArray;}// 先计算出奇数的个数count，然后用双指针来遍历，一个从头遍历到count，一个从数组尾部遍历到count。// 从前向后找到一个偶数的下标，从后向前找到一个奇数的下标，然后交换对应的值。// 直到遍历完整个数组。时间复杂度为O（n），空间复杂度为O（1）private static int[] reOrderArray3(int[] arr) {// 头部指针int front =0;// 尾部指针int end = arr.length-1;while(front < end){while (front < arr.length && arr[front] % 2 == 1){// 从前向后找偶数，如果找到(即arr[front] % 2 == 0)，则front位置不移动front ++;}while (end > 0 && arr[end] % 2 == 0){// 从后往前找奇数，如果找到(即arr[end] % 2 == 1)，则end位置不移动end --;}if (front < end){// 将前面的偶数与后面奇数交换位置int temp = arr[front];arr[front] = arr[end];arr[end] = temp;}}return arr;}
}