題目來源：牛客網-劍指Offer專題
題目地址：調整數組順序使奇數位于偶數前面

題目描述

輸入一個整數數組，實現一個函數來調整該數組中數字的順序，使得所有的奇數位于數組的前半部分，所有的偶數位于數組的后半部分，并保證奇數和奇數，偶數和偶數之間的相對位置不變。

題目解析

對于這道題，有三種實現方式，時間復雜度分別為 $O(n^2)$、 $O(nlogn)$ 和 $O(n)$，下面我們來逐一介紹：

方法一：
思路類似于插入排序：遍歷 $array$ ，當遇到array[i]偶數時，就p=i+1位置開始尋找第一個奇數。如果找到了，則將array[p]移動到array[i]前面。否則，說明數組的調整已經完成，遍歷停止。

上圖是某次遇到偶數時的執行圖示，供大家理解。這個算法的時間復雜度為 $O(n^2)$。

public class Solution {public void reOrderArray(int [] array) {int size = array.length;for (int i = 0; i < size; i++) {if (array[i] % 2 == 0) {int p = i + 1;//尋找array[i]以后的第一個奇數while (p < size && array[p] % 2 != 1) p++;if (p < size) {//array[p]移動到array[i]的位置，且將保持相對位置不變int t = array[p];for (int j = p; j > i; j--) {array[j] = array[j - 1];}array[i] = t;} else {//說明已經完成了數組的調整break;}}}} }

方法二：
這個種做法的思路源于歸并排序，是我參考Cyril-廖思睿博客的思路（長見識了）。

如果你學了歸并排序，理解下面代碼不會有任何難度，詳情可以看注解（不懂留言也可 ）。算法時間復雜度為 $O(nlogn)$。

public class Solution {public void reOrderArray(int [] array) {if (array == null || array.length < 2) {return ;}orderProcess(array, 0, array.length - 1);}public void orderProcess(int [] array, int left, int right) {if (left == right) {return ;}int mid = left + ((right - left) >> 1);//進行劃分操作orderProcess(array, left, mid);orderProcess(array, mid + 1, right);//進行合并操作mergeOrder(array, left, mid, right);}//進行合并操作public void mergeOrder(int [] array, int left, int mid, int right) {int len = right - left + 1, pLeft = left, pRight = mid + 1, p = 0;//暫時存空間int temp[] = new int[len];//為了保持相對順序不變，先放左邊的奇數while (pLeft <= mid && array[pLeft]%2 == 1) {temp[p++] = array[pLeft++];}while (pRight <= right && array[pRight]%2 == 1) {temp[p++] = array[pRight++];}//為了保持相對順序不變，先放左邊的偶數while (pLeft <= mid) {temp[p++] = array[pLeft++];}while (pRight <= right) {temp[p++] = array[pRight++];}//將暫存空間中的數移回原數組中for (int k = 0; k < len; k++) {//注意相對位置array[left + k] = temp[k];}} }

方法三
這種方法是一種空間換時間的一種策略，多開一個專門用于存儲的偶數的數組 $evens$，在遍歷的過程中，將偶數按原來的相對順序放到 $evens$ 中；而奇數也在原數組中按原來的相對順序，進行緊湊操作（直接放到上一個奇數后面）。如下圖所示：

最后，將偶數（$evens$）接到回奇數（原數組）后面，就完成了我們的調整，時間復雜度為$O(n)$。

public class Solution {public void reOrderArray(int [] array) {int size = array.length, s1 = 0, s2 = 0;//專門用于存儲的偶數的數組int [] evens = new int[size];for (int i = 0; i < size; i++) {//篩選過程，將奇數和偶數分開if (array[i] % 2 == 1) {array[s1++] = array[i];} else {evens[s2++] = array[i];}}//將偶數接到奇數后面for (int i = 0; i < s2; i++) {array[s1++] = even[i];}} }

---

如果本文對你有所幫助，要記得點贊哦~

總結

以上是生活随笔為你收集整理的剑指Offer #13 调整数组顺序使奇数位于偶数前面 | 图文详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。