待排序数组是否能被较均匀地划分对快速排序的性能有重要影响,因此枢轴元素的选取非常重要。有

Question

待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素。下面是随机化快速排序划分的伪代码——利用原有的快速排序的划分操作，请填充其中的空缺处。其中，RANDOM(i,j)表示随机取i到j之间的一个数，包括i和j。

(2)随机化快速排序是否能够消除最坏情况的发生? (10)。(是或否)

Answer 1

正确答案：由于随机化的快速排序的划分调用了传统的快速排序算法的PARTITION操作而传统的划分每次以数组的最后一个元素作为枢轴元素因此随机化的划分操作中每次先随机获得一个元素将其与最后一个元素交换。随机化的快速排序消除了输入数据的不同排列对算法性能的影响降低了极端不均匀划分的概率但不能保证不会导致最坏情况的发生。
由于随机化的快速排序的划分调用了传统的快速排序算法的PARTITION操作，而传统的划分每次以数组的最后一个元素作为枢轴元素，因此随机化的划分操作中每次先随机获得一个元素，将其与最后一个元素交换。随机化的快速排序消除了输入数据的不同排列对算法性能的影响，降低了极端不均匀划分的概率，但不能保证不会导致最坏情况的发生。