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

10 万数据 0.009s 是正常的；

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

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

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)

最后的代码写的有问题
  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)