golang实现快速排序排有序数组是效率低的问题

问题描述：

如果不加随机索引 10万有序数据，排序耗时17秒左右
如果增加随机索引（代码如下）耗时4到5秒

p := rand.Intn(right-left)+left+1
swap(arr, left,p)

我最初还以为是如下图 rand.Seed函数的问题。结果发现如果不加rand生成随机数会更慢。跟rand.Seed函数其实没有关系，增加了rand生成随机数还算是优化了耗时。。。
图片描述
所以，golang的快速排序排有序数组为什么这么慢？有懂行的吗？

404_ 2023-06-13

源自：快速排序法 1-7 为快速排序添加随机化

收起

1回答

提问者 404_ 2023-06-13 12:17:56

但是排序10万的随机数组，耗时0.009s。速度还是可以的

收起回答

liuyubobobo #1

10 万数据 0.009s 是正常的；
对于没有使用随机优化的快排，10 万有序数据 17 秒也是正常的；

但是，如果是同样的代码，使用了随机优化以后，4-5 秒不是特别正常。你有时间把完整的可执行的全部相关代码文件贴一下，我找时间看一下。谢谢。

2023-06-15 07:31:47

提问者 404_ 回复 liuyubobobo #2

func QuickSortV2(arr []int) {
    sort(arr, 0, len(arr)-1)
}
 
func sort(arr []int, left int, right int) {
    if left >= right {
        return
    }
    p := paration(arr, left, right)
    sort(arr, left, p-1)
    sort(arr, p+1, right)
}
 
func paration(arr []int, left int, right int) int {
    // 在 left和right之间生成一个随机索引
    //seed := time.Now().UnixNano() // seed函数耗时太长，目前没有找到更好的方法
    //rand.Seed(seed)
    //p := rand.Intn(right-left) + left + 1
    //swap(arr, left, p)
     
    p := rand.Int()%(right-left+1) + left
    arr[p], arr[right] = arr[right], arr[p]
    swap(arr, left, p)
     
    // left+1到j直接都是小于v的，j+1到i-1直接都是大于v的
    j := left
    for i := left; i <= right; i++ {
        if arr[i] < arr[left] {
            j++
            swap(arr, i, j)
        }
    }
    swap(arr, left, j)
    return j
}
 
func swap(arr []int, i int, j int) {
    tmp := arr[i]
    arr[i] = arr[j]
    arr[j] = tmp
}

如果使用这个随机调换数组中元素位置的方式，耗时5秒多

        // 在 left和right之间生成一个随机索引
    //seed := time.Now().UnixNano() // seed函数耗时太长，目前没有找到更好的方法
    //rand.Seed(seed)
    //p := rand.Intn(right-left) + left + 1
    //swap(arr, left, p)

如果使用这个随机调换数组中元素位置的方式，耗时3秒多

        p := rand.Int()%(right-left+1) + left
    arr[p], arr[right] = arr[right], arr[p]
    swap(arr, left, p)

2023-06-15 11:44:59

提问者 404_ #3

最后的代码写的有问题
  p := rand.Int()%(right-left+1) + left
    arr[p], arr[right] = arr[right], arr[p]
    swap(arr, left, p)
应该是：
    p := rand.Int()%(right-left+1) + left
    swap(arr, left, p)