[[411577]]

本文轉載自微信公眾號「光城」，作者 lightcity 。轉載本文請聯系光城公眾號。

最近打算重拾算法，從0跟著acwing走一遍，順便用Go實現一下。

今天的目標是學習快排，使用Go寫。

學習自acwing。

輸入：

3 
1 3 2 

輸出：

1 2 3 

快排思想：

1.定義pivot

2.根據pivot劃分區間

3.遞歸子問題

pivot可以隨機選擇，例如：arr[l]、arr[r] 等等。

當遞歸時有兩種選擇，一種是取j，需要保證pivot不取arr[r]，防止死循環。

本文實現用這個：

pivot := arr[(l+r)>>1] 
quickSort(arr, l, j) 
quickSort(arr, j+1, r) 

另一種是取i，需要保證pivot不取arr[l]，防止死循環，同時不可以使用 arr[(l+r)>>1]這種，得向上取整，例如：arr[(l+r+1)>>1]。

本文實現用這個：

pivot := arr[(l+r+1)>>1] 
quickSortI(arr, l, i-1) 
quickSortI(arr, i, r) 

最后補充幾個go知識。

1.輸入

go中處理輸入，使用fmt.Scan，將地址傳進去，這里我實現了一個函數，后面可以直接復用。

// DoBlackInput 處理空格輸入為數組 
func DoBlackInput(n int) []int { 
 arr := make([]int, n) 
 for i := 0; i < n; i++ { 
  fmt.Scan(&arr[i]) 
 } 
 return arr 
} 

2.交換

如何快速交換兩個元素。

a, b = b, a 

這樣便可以快速交換了。

3.do...while{}

可以使用：

for { 
    // do something 
    if true { 
      break 
    } 
  } 

4.i++與++i

不支持++i、--i。

最后，完整代碼如下：

package main 
 
import "fmt" 
 
// DoBlackInput 處理空格輸入為數組 
func DoBlackInput(n int) []int { 
 arr := make([]int, n) 
 for i := 0; i < n; i++ { 
  fmt.Scan(&arr[i]) 
 } 
 return arr 
} 
 
// quickSort 取j 
func quickSort(arr []int, l int, r int) { 
 if l >= r { 
  return 
 } 
 pivot := arr[(l+r)>>1] 
 i := l - 1 
 j := r + 1 
 for i < j { 
  for { 
   i++ 
   if arr[i] >= pivot { 
    break 
   } 
  } 
  for { 
   j-- 
   if arr[j] <= pivot { 
    break 
   } 
  } 
  if i < j { 
   arr[i], arr[j] = arr[j], arr[i] 
  } 
 } 
 quickSort(arr, l, j) 
 quickSort(arr, j+1, r) 
} 
 
// quickSort 取i 
func quickSortI(arr []int, l int, r int) { 
 if l == r { 
  return 
 } 
 pivot := arr[(l+r+1)>>1] 
 i := l - 1 
 j := r + 1 
 for i < j { 
  for { 
   i++ 
   if arr[i] >= pivot { 
    break 
   } 
  } 
  for { 
   j-- 
   if arr[j] <= pivot { 
    break 
   } 
  } 
  if i < j { 
   arr[i], arr[j] = arr[j], arr[i] 
  } 
 } 
 quickSortI(arr, l, i-1) 
 quickSortI(arr, i, r) 
} 
func main() { 
 var n int 
 fmt.Scan(&n) 
 arr := DoBlackInput(n) 
 quickSort(arr, 0, n-1) 
 for _, v := range arr { 
  fmt.Printf("%d ", v) 
 } 
}