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