Go数据结构与算法基础之快速排序
本文转载自微信公众号「光城」，数据算法速排作者 lightcity 。结构基础转载本文请联系光城公众号。数据算法速排
最近打算重拾算法，结构基础从0跟着acwing走一遍，数据算法速排顺便用Go实现一下。结构基础
今天的数据算法速排目标是学习快排，使用Go写。结构基础
学习自acwing。数据算法速排
输入：
3 1 3 2输出：
1 2 3快排思想：
1.定义pivot
2.根据pivot划分区间
3.递归子问题
pivot可以随机选择，结构基础例如：arr[l]、云南idc服务商数据算法速排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) } }