随机数一定在要排序的数组中吗？

Question

老师，您好
我有个疑问，使用随机数来优化快速排序，产生的随机数在 l 到 r 范围内，但这个数一定是在要排序的数组中吗？

Answer 1

liuyubobobo 2019-02-15 14:36:52

一定。

我们的目的是使用待排序区间中的一个随机数字作为标定点，而不是固定的使用待排序区间的最左边的数字arr[l]作为标定点，否则就会出现当待排序数组是近乎有序的时候，退化为O(n^2)的问题。

在这里，要注意我们的递归函数：

void _quickSort(T arr[], int l, int r)

他的语义是对arr[l...r]这个区间进行排序，所以，这个过程不能涉及[l...r]区间以外的元素。

实际按照你的想法，修改一下程序，执行一下，看看结果是怎样的？排序能不能成功完成，如果不能，使用一个小的数据量实际跟踪一下，看看为什么，在哪里出了问题？然后再理解一下我们的算法？：）

加油！

• 提问者 iiiboy #1

  非常感谢! 是我自己糊涂了，原先想成交换随机数的值，其实随机数是作为索引。给老师带来麻烦了，下次自己多多调试