算法技术手册 – 排序 – 快速排序

待补充:非递归版本。

快速排序和前面的中值排序非常类似。

分为partition和sort主体两个部分。

1.partition
和前面求第k大的数用到的思路非常类似。
(0)确定一个pivotIndex
(1)交换a[right]和a[pivotIndex]
(2)i=store=left,i从left到right-1,注意要包含right-1!!(不用包含right,因为里面是pivot)
(3)在(2)过程中,如果a[i] (4)完成上述步骤后,交换a[store]和a[right]
(5)返回store下标

2.qsort
(0)仅当left (1)根据partition确定下标pivot
(2)qsort(left,pivot-1)
(3)qsort(pivot+1,right)

该算法证明非常复杂,时间复杂度平均O(nlogn),最差O(n^2)

排序题:
排序

关于快速排序的优化:

(1)随机选择中枢值。
(2)采用k中值:在[left, right]之间随机选择k个中值,然后取k的中值作为中枢值,一般k=3。
(3)平衡切分:如果很多值等于中枢值,会导致子问题不平衡,可以轮换的将等于中枢值的换位一次到左、右两个子数组中。
(4)优化递归次序,如果堆积的递归栈过大,不利于系统处理,可以优先处理小数组,使得栈尽可能的浅。
(5)当数组过小时,插入排序将远好于快速排序,因此,一般当规模小时将切换到插入排序。
三中值 + 小规模插入排序可以使得快速排序的性能提升20% ~ 25%。
内观排序(IntroSort):1997年由Musser提出,它将检测内部递归深度,如果超过log(n),将切换到堆排序。SGI的STL就使用了内观排序作为默认的排序算法。

Leave a Reply

Your email address will not be published.