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

本文转载自微信公众号「光城」，数据算法速排作者 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]这种，得向上取整，b2b信息网例如：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)  } } 

很赞哦!（756）