[[411577]]

本文轉(zhuǎn)載自微信公眾號「光城」，作者 lightcity 。轉(zhuǎn)載本文請聯(lián)系光城公眾號。

最近打算重拾算法，從0跟著acwing走一遍，順便用Go實(shí)現(xiàn)一下。

今天的目標(biāo)是學(xué)習(xí)快排，使用Go寫。

學(xué)習(xí)自acwing。

輸入：

3 
1 3 2 

輸出：

1 2 3 

快排思想：

1.定義pivot

2.根據(jù)pivot劃分區(qū)間

3.遞歸子問題

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

當(dāng)遞歸時(shí)有兩種選擇，一種是取j，需要保證pivot不取arr[r]，防止死循環(huán)。

本文實(shí)現(xiàn)用這個(gè)：

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

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

本文實(shí)現(xiàn)用這個(gè)：

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

最后補(bǔ)充幾個(gè)go知識。

1.輸入

go中處理輸入，使用fmt.Scan，將地址傳進(jìn)去，這里我實(shí)現(xiàn)了一個(gè)函數(shù)，后面可以直接復(fù)用。

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

2.交換

如何快速交換兩個(gè)元素。

a, b = b, a 

這樣便可以快速交換了。

3.do...while{}

可以使用：

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

4.i++與++i

不支持++i、--i。

最后，完整代碼如下：

package main 
 
import "fmt" 
 
// DoBlackInput 處理空格輸入為數(shù)組 
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) 
 } 
}