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

来源：3-6 随机化快速排序法

iiiboy

2019-02-15

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

写回答

1回答

liuyubobobo

2019-02-15

已采纳

一定。

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

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

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

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

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

加油！

iiiboy

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

2019-02-15

共1条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1