Go 常見算法面試題篇：高效調整數組數值順序
題目
今天來看一個考察程序員基本功的數組面試題，看起來仍然很簡單，不過通過這個題目的不同解法，可以快速檢驗你是初級程序員還是資深程序員，一起來看下吧：
輸入一個整數數組，實現一個函數來調整該數組中數字的順序，使得所有奇數位於數組的前半部分，所有偶數位於數組的後半部分。
解法一
對於新人而言，可以很快寫出下面這樣的實現代碼：
func reOrderArrayV1(arr []int) []int {
var oddArr, evenArr []int
for _, value := range arr {
if value % 2 == 0 {
evenArr = append(evenArr, value)
} else {
oddArr = append(oddArr, value)
}
}
return append(oddArr, evenArr...)
}非常簡單，先聲明兩個數組切片，分別用於存儲奇數和偶數，然後遍歷待排序的數組切片，根據是否可以被 2 整除將切片數據分發到偶數和奇數切片，最後將偶數切片數據追加到奇數切片之後作爲新的切片返回。
爲上面這段代碼編寫測試代碼：
func main() {
arr := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
fmt.Println("排序前:", arr)
fmt.Println("排序後:", reOrderArrayV1(arr))
}執行之後打印結果如下，說明代碼可以正常工作：
解法二
上面的實現雖然簡單易懂，不過擴展性很差，比如現在是按照奇偶數排序，如果換一下排序條件，變成按照是否可以被 3 整除，或者按照正負數進行排序，則需要重寫整個排序方法實現代碼。
實現相同功能的代碼，在滿足最基本的正確性的基礎上，新人和老鳥的區別往往就是體現在擴展性、魯棒性、高性能這些更高層級的代碼藝術上。
下面我們從擴展性的角度出發，將排序條件抽取出來作爲可定製的閉包參數從外部傳入排序函數：
// 根據指定閉包對數組切片排序
func reOrderArrayV2(arr []int, orderFunc func(int) bool) []int {
// 小於等於1個元素無需處理
if arr == nil || len(arr) <= 1 {
return arr
}
// 設置兩個指針，從頭尾往中間移動
i := 0
j := len(arr) - 1
// 頭指針不能越過尾指針，否則退出
// 以奇偶數排序爲例，i 從左到右尋找偶數，j 從右到左尋找奇數
// 該循環執行完畢後，i == j，且 i 左側的都是奇數，j 右側的都是偶數，也就完成了順序調整
for i < j {
// 如果不符合條件，則頭指針後移，否則中斷
// 以 orderFunc 爲偶數判斷函數爲例，返回 false 表示是奇數
// 題目要求奇數排在前面，因此，當 i 對應值是奇數時，往後移一位，然後繼續下一個循環，直到 i==j 或者遇到第一個偶數中斷
for i < j && !orderFunc(arr[i]) {
i++
}
// 如果符合條件，則尾指針前移，否則中斷
// 還是以 orderFunc 爲偶數判斷函數爲例，返回 true 表示是偶數
// 題目要求偶數排在後面，因此，當 j 對應值是偶數時，往前移一位，然後繼續下一個循環，直到 j==i 或者遇到第一個奇數中斷
for i < j && orderFunc(arr[j]) {
j--
}
// 如果 i < j，則交換對應值的位置
// 以奇偶數爲例，此時 arr[i] 是偶數，arr[j] 是奇數，則交換兩個值，將奇數放到前面，偶數放到後面
if i < j {
arr[i], arr[j] = arr[j], arr[i]
}
// 繼續下一個循環，直到 i==j，此時 i 左側都是奇數，j 右側都是偶數，所有奇數都排到了偶數前面
}
return arr
}
// 排序條件：是否是偶數
func isEven(num int) bool {
return num & 1 == 0
}這樣一來，reOrderArrayV2 函數就與具體的排序條件解耦了，我們可以通過外部參數傳入任意的排序條件：
arr := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
fmt.Println("排序前:", arr)
fmt.Println("排序後:", reOrderArrayV2(arr, isEven))打印結果如下，表明排序成功：
下次你想通過正負數、是否可以被 3 整除之類的排序條件做排序，只需要編寫對應的排序條件判定函數，然後傳入 reOrderArrayV2排序函數即可，排序函數本身無需做任何調整：
// 是否是整數（爲 true 的值放在後面）
func isPositive(num int) bool {
return num > 0
}
// 是否可以被 3 整除（爲 true 的值放在後面）
func canBeDividedBy3(num int) bool {
return num % 3 == 0
}性能對比
從擴展性上看，顯然第二種解法比第一種好很多，除此之外，我們在第二種解法中還通過指針移動和位運算的方式優化了程序的性能，具體對性能的影響如何，可以編寫基準測試來驗證：
package main
import (
"testing"
)
func BenchmarkReOrderArrayV1(b *testing.B) {
for n := 0; n < b.N; n++ {
arr := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
reOrderArrayV1(arr) // run reOrderArrayV1(arr) b.N times
}
}
func BenchmarkReOrderArrayV2(b *testing.B) {
for n := 0; n < b.N; n++ {
arr := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
reOrderArrayV2(arr, isEven) // run reOrderArrayV2(arr, isEven) b.N times
}
}運行上面的基準測試代碼：
可以看到 reOrderArrayV2 排序函數的單次運行時間要比 reOrderArrayV1 快 6 倍，性能有了很顯著的提升。
此外，還可以加上 -benchmem 選項對比下兩種解法的內存分配情況（空間複雜度），由於第一種解法需要引入額外的數組切片存儲中間數據，所以顯然第二種解法的空間複雜度更優：
可以看到，第一種解法每次要分配 368B 的內存空間，而第二種解法不需要額外分配內存空間。
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/JY0uwTWqPbfDllUgD3QaeA