poo*_*ank 2 sorting algorithm quicksort data-structures
我正在学习快速排序.我知道当分量值执行不平衡分区时,快速排序执行得很糟糕,因此第一个元素或最后一个元素不是一个好选择,因为如果列表几乎排序,则分区将是不平衡的.
当我搜索我发现2个选项:
一种是在低(最低指数)和向上(最高指数)之间随机选择一个支点.这似乎是一个安全的选择,但随机数生成器是耗时的.
第二个是取所有元素的中位数.此选项很昂贵,因此第一个,最后一个和中间元素的中位数可用作枢轴元素.
哪种方法被证明是最有效的快速排序？..有没有其他方法可用于选择枢轴元素？