劍指Offer面試題：13.調整數組順序使奇數位于偶數前面
題目：輸入一個整數數組，實現一個函數來調整該數組中數字的順序，使得所有奇數位于數組的前半部分，所有偶數位于數組的后半部分。例如有以下一個整數數組：12345，經過調整后應該為：15342、13542、13524等等。
一、題目：調整數組順序使奇數位于偶數前面
題目：輸入一個整數數組，實現一個函數來調整該數組中數字的順序，使得所有奇數位于數組的前半部分，所有偶數位于數組的后半部分。
例如有以下一個整數數組：12345，經過調整后可以為：15342、13542、13524等等。
二、解題思路
2.1 基本解法
如果不考慮時間復雜度，最簡單的思路應該是從頭掃描這個數組，每碰到一個偶數時，拿出這個數字，并把位于這個數字后面的所有數字往前挪動一位。挪完之后在數組的末尾有一個空位，這時把該偶數放入這個空位。由于每碰到一個偶數就需要移動O(n)個數字，因此總的時間復雜度是O(n2)。
2.2 高效解法
這里可以參考快速排序的思想，快速排序的基本思想是：通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序的目的。
因此，我們可以借鑒快速排序的思想，通過設置兩個指針來進行交換操作，從而減少移動次數，提高效率：
Step1.第一個指針初始化時指向數組的第一個數字，它只向后移動；
Step2.第二個指針初始化時指向數組的最后一個數字，它只向前移動。
Step3.在兩個指針相遇之前，第一個指針總是位于第二個指針的前面。如果第一個指針指向的數字是偶數，并且第二個指針指向的數字是奇數，我們就交換這兩個數字。
下圖展示了調整數組{1,2,3,4,5}使得奇數位于偶數前面的過程：
三、解決問題
3.1 代碼實現
?。?）基本功能實現
public static void ReorderOddEven(int[] datas) { if (datas == null || datas.Length <= 0) { return; } int begin = 0; int end = datas.Length - 1; int temp = -1; while (begin < end) { // 向后移動begin，直到它指向偶數 while (begin < end && datas[begin] % 2 != 0) { begin++; } // 向前移動pEnd，直到它指向奇數 while (begin < end && datas[end] % 2 == 0) { end--; } if (begin < end) { // 交換偶數和奇數 temp = datas[begin]; datas[begin] = datas[end]; datas[end] = temp; } } }
怎么樣，看起來是不是和快速排序的代碼如出一轍？
（2）可擴展性實現
如果把題目改成把數組中的數按照大小分為兩部分，所有負數都在非負數的前面，又或者改改，變成把數組中的數分為兩部分，能被3整除的數都在不能被3整除的數的前面。面對需求的變化，我們發現代碼變化的部分很小，因此從可擴展性的角度考慮，我們可以改寫上面的代碼如下，這里利用了.NET中的“函數指針”—委托來實現。
?、俜椒▽崿F
public static void ReorderOddEven(int[] datas, Predicate<int> func) { if (datas == null || datas.Length <= 0) { return; } int begin = 0; int end = datas.Length - 1; int temp = -1; while (begin < end) { // 向后移動begin，直到它指向偶數 while (begin < end && !func(datas[begin])) { begin++; } // 向前移動pEnd，直到它指向奇數 while (begin < end && func(datas[end])) { end--; } if (begin < end) { // 交換偶數和奇數 temp = datas[begin]; datas[begin] = datas[end]; datas[end] = temp; } } }
這里使用了.NET中的預定義委托Predicate，有不了解預定義委托的朋友可以閱讀我另一篇博文：《.NET中那些所謂的新語法之三》，這里就不再贅述了。
②如何調用
// 判斷奇數還是偶數 ReorderHelper.ReorderOddEven(numbers, new Predicate<int>((num) => num % 2 == 0)); // 判斷是能否被3整除 ReorderHelper.ReorderOddEven(numbers, new Predicate<int>((num) => num % 3 == 0));
這里使用了.NET中的Lambda表達式，同樣，有不了解Lambda表達式的朋友也可以閱讀我的另一篇博文：《.NET中那些所謂的新語法之三》，這里也就不再贅述了。
3.2 單元測試
首先，這里封裝了一個用于比較兩個數組中的元素值是否相等的輔助方法：
// 輔助方法：對比兩個數組是否一致 public bool ArrayEqual(int[] ordered, int[] expected) { if (ordered.Length != expected.Length) { return false; } bool result = true; for (int i = 0; i < ordered.Length; i++) { if (ordered[i] != expected[i]) { result = false; break; } } return result; }
（1）功能測試
// Test1:輸入數組中的奇數、偶數交替出現 [TestMethod] public void ReorderTest1() { int[] numbers = { 1, 2, 3, 4, 5, 6, 7 }; int[] expected = { 1, 7, 3, 5, 4, 6, 2 }; ReorderHelper.ReorderOddEven(numbers); Assert.AreEqual(ArrayEqual(numbers, expected), true); } // Test2:輸入數組中的所有偶數都出現在奇數的前面 [TestMethod] public void ReorderTest2() { int[] numbers = { 2, 4, 6, 1, 3, 5, 7 }; int[] expected = { 7, 5, 3, 1, 6, 4, 2 }; ReorderHelper.ReorderOddEven(numbers); Assert.AreEqual(ArrayEqual(numbers, expected), true); } // Test3:輸入數組中的所有奇數都出現在偶數的前面 [TestMethod] public void ReorderTest3() { int[] numbers = { 1, 3, 5, 7, 2, 4, 6 }; int[] expected = { 1, 3, 5, 7, 2, 4, 6 }; ReorderHelper.ReorderOddEven(numbers); Assert.AreEqual(ArrayEqual(numbers, expected), true); }
（2）特殊輸入測試
// Test4:輸入的數組只包含一個數字-奇數 [TestMethod] public void ReorderTest4() { int[] numbers = { 1 }; int[] expected = { 1 }; ReorderHelper.ReorderOddEven(numbers); Assert.AreEqual(ArrayEqual(numbers, expected), true); } // Test5:輸入的數組只包含一個數字-偶數 [TestMethod] public void ReorderTest5() { int[] numbers = { 2 }; int[] expected = { 2 }; ReorderHelper.ReorderOddEven(numbers); Assert.AreEqual(ArrayEqual(numbers, expected), true); } // Test6:NULL指針 [TestMethod] public void ReorderTest6() { int[] numbers = null; int[] expected = null; ReorderHelper.ReorderOddEven(numbers); Assert.AreEqual(numbers, expected); }
?。?）測試結果
?、儆美ㄟ^情況
?、诖a覆蓋率
浙公網安備 33010602011771號