輸入一個整數(shù)數(shù)組住闯，實現(xiàn)一個函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分拂酣，所有的偶數(shù)位于位于數(shù)組的后半部分秋冰，并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對位置不變婶熬。
注意
本題和 lintcode 上的快排變形題有區(qū)別剑勾，快排本身無法保證排序的穩(wěn)定性，題目要求偶數(shù)和奇數(shù)的相對位置不能變
代碼
- 插入排序思想赵颅，空間復雜度為O（1）虽另，時間復雜度為O（N^2）
public class Solution {
public void reOrderArray(int [] array) {
if (array == null || array.length == 0) {
return;
}
for (int i = 0; i < array.length; i++){
// i 位置是奇數(shù)
if (array[i] % 2 == 1){
int temp = array[i];
int j = i - 1;
// j 的位置為偶數(shù)
// j>=0 防止 j=i-1 越界
// 把 i 位置空出來，把 i 位置前面的偶數(shù)全部后移一位饺谬，把 array[i] 位置的奇數(shù)插入到新的位置
while (j >= 0 && array[j] % 2 == 0){
array[j + 1] = array[j];
j--;
}
// 注意此處是 j+1 不是 j
array[j + 1] = temp;
}
}
}
}
- 歸并排序捂刺，時間復雜度 O(nlogn)，空間復雜度 O(n)
public class Solution {
public void reOrderArray(int [] array) {
if (array == null || array.length == 0) {
return;
}
int[] des = new int[array.length];
MergeMethod(array, des, 0, array.length - 1);
}
public void MergeMethod(int[] array, int [] des, int start, int end){
if (start < end){
int mid = (start + end) / 2;
MergeMethod(array, des, start, mid);
MergeMethod(array, des, mid + 1, end);
Merge(array, des, start, mid, end);
}
}
public void Merge(int[] array, int[] des, int start, int mid, int end){
int i = start;
int j = mid + 1;
int k = start;
// 四個 while 其實是同時執(zhí)行募寨，沒有先后順序族展，因為 array[i] 和 array[j] 同一時刻只能滿足一個 while
// 把奇數(shù)歸并
while(i <= mid && array[i] % 2 == 1){
des[k++] = array[i++];
}
while(j <= end && array[j] % 2 == 1){
des[k++] = array[j++];
}
// 把偶數(shù)歸并
while(i <= mid){
des[k++] = array[i++];
}
while(j <= end){
des[k++] = array[j++];
}
for(int m = start; m <= end; m++){
array[m] = des[m];
}
}
}
- 既然開辟了新的數(shù)組，完全可以從頭掃描兩遍拔鹰，第一遍遇到奇數(shù)加入數(shù)組仪缸，第二遍遇到偶數(shù)加入數(shù)組，最后把新數(shù)組中的值逐個復制到原數(shù)組中去
public class Solution {
public void reOrderArray(int [] array) {
if (array == null || array.length == 0) {
return;
}
int[] list = new int[array.length];
int index = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] % 2 == 1) {
list[index++] = array[i];
}
}
for (int i = 0; i < array.length; i++) {
if (array[i] % 2 == 0) {
list[index++] = array[i];
}
}
for (int i = 0; i < array.length; i++) {
array[i] = list[i];
}
}
}
