Go数据结构与算法基础之快速排序

本文转载自微信公众号「光城」，作者 lightcity 。转载本文请联系光城公众号。

最近打算重拾算法，从0跟着acwing走一遍，顺便用Go实现一下。

今天的目标是学习快排，使用Go写。

学习自acwing。

输入：

3 
1 3 2 

输出：

1 2 3 

快排思想：

定义pivot

根据pivot划分区间

递归子问题

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) 
 } 
}