体育彩票销售站联盟

谈谈随机快速排序

扣丁部落2018-11-07 14:19:53

    说实话,昨天讲到的快速排序的实现其实是有很大问题的。设想一下,倘若这是一个近乎于有序的数组,就像昨天那样,设L为每次排序最左的元素的下标值,我们选择arr[L]作为基准点,即数组的元素几乎都比arr[L]大,这样就会被分成很不平均的两份,而就如下图我们看到的那样,这个算法的时间复杂度就退化成了O(n^2)。如下图所示:

        设想一下,当我们选择的基准点由确定的变成不确定的,即变成随机的,若数组的元素个数为N,我们以随机的方式选择基准点,这样选择到一个最小的值概率为1/N,而在次轮选择到次轮排序中最小值概率为1/N-1,第三轮为1/N-2,此时每轮选择到最小值的概率(1/N)*(1/N-1)*(1/N-2)……,倘若N足够大,这个概率近乎为0。

        修改一下代码。

        

    而__quickSort()不需要做任何改变,因为基准点的选择是在__merge()实现的。