golang快速排序改进版

发条家的橙子 · · 608 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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)
}

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

本文来自:简书

感谢作者:发条家的橙子

查看原文:golang快速排序改进版

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

608 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传