(3)Go实现单路快排和随机快排

快速排序和递归排序一样，思想都是分治法，即将问题划分为若干相互独立的个小问题，这些问题和该问题具有相同的特征，将这些小问题解决后，该问题也解决了。
在最好的情况下，每次都平均分成2半，n个数字分log2N次能分完，每次遍历n个数值，时间复杂度为log2Nn=logNn。在最差的情况下，每次分都分成1和n-1半，这样要n次才能分完，时间复杂度会变成 n*n

不同点在于递归排序是直接将数组平均分组，而快速排序是以某个值v为基准，分组后，左边的值小于v，右边的值大于v，等于的情况放左边右边都可以，如下图示：

以数组首个值4为基准示例，分组后左边的值都小于4，右边的值都大于4，之后分别继续对
左边小于4的部分和右边大于4的部分进行分组，依此完成排序

单路快速排序的实现
// 单路快速排序,前闭后闭
func QuickSort1(arr []int, l, r int) {
    if l >= r {
        return
    }
    p := Partition1(arr, l, r)
    QuickSort1(arr, l, p-1)
    QuickSort1(arr, p+1, r)
}

func Partition1(arr []int, l, r int) int {
    v := arr[l]
    j := l
    for i := l + 1; i <= r; i++ {
        if arr[i] < v {
            j++
            arr[j], arr[i] = arr[i], arr[j]
        }
    }
    // 如果没有发生交换,j 最终是和自己发生交换,数组不变
    arr[j], arr[l] = v, arr[j]
    return j
}

测试
// 测试排序结果是否正确
func isTrue(nums []int) {
    b := true
    for i := 1; i < count; i++ {
        if nums[i-1] > nums[i] {
            fmt.Println("排序错误", nums[i-1], nums[i])
            b = false
            break
        }
    }
    if b {
        fmt.Println("排序正确")
    }
}



func main() {
    const count = 10000
        
    t := time.Now()
    quick_sort.QuickSort1(nums, 0, len(nums)-1)
    fmt.Println("基本快速排序时间:", t.Sub(time.Now()))
    isTrue(nums)
}
测试结果
1）数组完全随机
    nums := []int{}
    for i := 0; i < count; i++ {
        nums[i] = rand.Intn(count )
    }

基本快速排序时间: -1.042074ms
排序正确

2）数组有序
    nums := []int{}
    for i := 0; i < count; i++ {
        nums[i] = count-i
    }
    
基本快速排序时间: -161.286566ms
排序正确

分析：两者时间差距100多倍，原因是每次都取数组首个值为基准，这样分区后左右数组及不平衡，
在最坏的情况下，快排的时间复杂度会退化成O(n^2)，如下图示：

解决方法是不要每次都取首个字母为基准，而是随机取一个数为基准，改动后的快排如下：
// 单路随机快排
func QuickSort2(arr []int, l, r int) {
    if l >= r {
        return
    }

    // 随机数为基准
    p := Partition2(arr, l, r)
    QuickSort3(arr, l, p-1)
    QuickSort3(arr, p+1, r)
}

func Partition2(arr []int, l, r int) int {
    // 随机取1个值为基准
    randIndex := randInt(l, r)
    arr[l], arr[randIndex] = arr[randIndex], arr[l]
    v := arr[l]

    j := l
    for i := l + 1; i <= r; i++ {
        if arr[i] < v {
            j++
            arr[j], arr[i] = arr[i], arr[j]
        }
    }

    arr[j], arr[l] = v, arr[j]
    return j
}

func randInt(l, r int) int {
    rand.Seed(time.Now().UnixNano())
    return l + rand.Intn(r-l)
}

测试单路快排和单路随机快排：
    const count = 100000

    nums := []int{}
    for i := 0; i < count; i++ {
        nums[i] = count-i
    }

    t1 := time.Now()
    quick_sort.QuickSort1(nums, 0, len(nums)-1)
    fmt.Println("基本快速排序时间:", t1.Sub(time.Now()))
    isTrue(nums)

    t2 := time.Now()
    quick_sort.QuickSort2(nums, 0, len(nums)-1)
    fmt.Println("基本快速排序时间:", t2.Sub(time.Now()))
    isTrue(nums)

测试结果 //
基本快速排序时间: -14.446320539s
排序正确
----
快速随机排序排序时间: -782.599245ms
排序正确

结论：每次随机取值为基准，能避免快速排序往最坏的情况发展，加快排序时间。

继续测试，当数据存在大量重复元素时，结果又会怎样？
    const count = 100000
    for i := 0; i < count; i++ {
        nums2[i] = rand.Intn(5)
    }

测试结果
基本快速排序时间: -2.554524223s
排序正确
----
快速随机排序排序时间: -3.0671954s
排序正确

分析，当数组中存在大量重复元素，随机快排的速度反而不如基本快排，这是因为重复元素
会偏向左边或右边，会导致分区不平均，拖慢排序时间

解决方法由两个，双路快排或3路快排：

后续《（4）Go实现双路快排，3路快排及测试》：
https://www.jianshu.com/p/37d563d5eda4