[Go] Golang练习项目-快速排序的GO语言实现
快速排序首先选一个基准（你也可以认为是要放到排序后数组正确位置的元素）pivot，然后将数组按照选取的基准 pivot 进行划分。而选取 pivot 的方式又有很多种，所以快速排序具有很多版本。
总是选择第一个元素作为基准 pivot； 总是选择最后一个元素作为基准；（本文后续的实现就是依次为例） 随机的选择一个元素作为基准； 选择最中间的元素作为基准；
快速排序的关键是划分 partion() 。每一趟划分，我们就可以将作为 pivot 的值 x 放到排序数组的正确位置，并且将所有比 x 小的放到 x 的左边，所有比 x 大的元素放到 x 的右边。
package tools
//划分
func partition(arr *[]int,left int,right int)int{
privot:=(*arr)[right]
i:=left-1
for j:=left;j<right;j++{
if (*arr)[j]<privot{
i++
temp:=(*arr)[i]
(*arr)[i]=(*arr)[j]
(*arr)[j]=temp
}
}
temp:=(*arr)[i+1]
(*arr)[i+1]=(*arr)[right]
(*arr)[right]=temp
return i+1
}
//递归
func QuickSort(arr *[]int,left int,right int){
if left>= right{
return
}
privot:=partition(arr,left,right)
QuickSort(arr,left,privot-1)
QuickSort(arr,privot+1,right)
} 测试用例：
package tools
import (
"testing"
)
func TestQuickSort(t *testing.T) {
arr:=[]int{1,8,3,9,4,5,4,7}
t.Log(arr)
QuickSort(&arr,0,len(arr)-1)
t.Log(arr)
}go test -v sorts_test.go sorts.go
文章转载自公众号(景寓)
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-08-17 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
