【Go数据结构与算法基础】快速排序
【Go数据结构与算法基础】快速排序
公众号guangcity
发布于 2021-07-30 10:45:13
发布于 2021-07-30 10:45:13
【Go数据结构与算法基础】快速排序
最近打算重拾算法，从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)
}
}
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-07-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录