golang快速排序改进版

package main
import (
 "fmt"
 "math/rand"
)
// 如果数量小于13直接用插入排序
func SortForMerge(arr []int, left, right int) {
 for i:=left; i<=right; i++ {
 temp := arr[i]
 var j int
 for j=i; j>left && temp < arr[j-1]; j-- {
 arr[j] = arr[j-1]
 }
 arr[j] = temp
 }
}
func swap(arr []int,i, j int) { // 数据交换
 arr[i], arr[j] = arr[j], arr[i]
}
func QuickSortX(arr []int, left, right int) {
 if right - left < 2 {
 SortForMerge(arr, left, right) // 如果数量小于3直接用插入排序
 } else { // 使用快速排序
 // 随机找一个数字
 swap(arr, left, rand.Int()%(right-left+1) + left )
 vdata := arr[left] // 坐标数据,比我小往左,大往右
 lt := left // < vdata
 gt := right + 1 // > vdata
 i := left+1 // == vdata
 for i < gt {
 if arr[i] > vdata {
 swap(arr, gt-1, i) //移动到大于的地方
 gt--
 } else if arr[i] < vdata {
 swap(arr, i, lt+1) //移动到小于的地方
 lt++ //前进循环
 i++
 } else {
 i++
 }
 }
 swap(arr, lt, left)
 QuickSortX(arr, left, lt-1) //递归处理小于那一段
 QuickSortX(arr, gt, right) //递归处理大于那一段
 }
}
func main() {
 arr := []int{3, 5, 2, 1, 5, 6, 9, 0}
 fmt.Println("排序前:", arr)
 QuickSortX(arr, 0 , len(arr)-1)
 fmt.Println("排序后:", arr)
}

有疑问加站长微信联系(非本文作者)

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
• 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传