方式一
类似于冒泡排序法
public class Solution { public void reOrderArray(int[] array) { if (array == null || array.length < 2) { return; } // 交换标记 boolean flag = false; int lastPos = 0; // end 是有序区指示 for (int end = array.length; end >= 0; end--) { for (int i = 0; i < end - 1; i++) { if ( (!isOddNumber(array[i])) && isOddNumber(array[i + 1])) { swap(i, i + 1, array); flag = true; // 记录最后的有序区边界 lastPos = i + 1; } } if (!flag) { break; } flag = false; // end-- 会将 end 减少一个 end = lastPos + 1; } } public static void swap(int indexA, int indexB, int[] arr) { arr[indexA] = arr[indexA] ^ arr[indexB]; arr[indexB] = arr[indexA] ^ arr[indexB]; arr[indexA] = arr[indexA] ^ arr[indexB]; return; } public static boolean isOddNumber(int val) { if (val % 2 == 1) { return true; } return false; } }
方法二
类似归并排序,采用递归,待大佬优化
public class Solution { public void reOrderArray(int[] array) { if (array == null || array.length < 2) { return; } mergeOrder(array, 0, array.length - 1); } public static void mergeOrder(int[] arr, int L, int R) { if (L == R) { return; } int mid = L + ((R - L) >> 1); mergeOrder(arr, L, mid); mergeOrder(arr, mid + 1, R); mergePartitionArr(arr, L, mid, R); } public static void mergePartitionArr(int[] arr, int L, int mid, int R) { int[] helpArr = new int[R - L + 1]; int pHelpArr = 0; int pLeftArr = L; int pRightArr = mid + 1; // 左边的奇数先放 while (pLeftArr <= mid && isOddNumber(arr[pLeftArr])) { helpArr[pHelpArr++] = arr[pLeftArr++]; } while (pRightArr <= R && isOddNumber(arr[pRightArr])) { helpArr[pHelpArr++] = arr[pRightArr++]; } // 左边的偶数先放 while (pLeftArr <= mid) { helpArr[pHelpArr++] = arr[pLeftArr++]; } while (pRightArr <= R) { helpArr[pHelpArr++] = arr[pRightArr++]; } for (int i = 0; i < helpArr.length; i++) { arr[L + i] = helpArr[i]; } return; } public static boolean isOddNumber(int val) { if (val % 2 == 1) { return true; } return false; } }