asd*_*sdf 2 sorting algorithm quicksort
鉴于数字列表:2 5 1 8 4 10 6 3 7 9 0
我理解的快速排序的实际实现,但我的功课问题是我没有:
枢轴的最佳选择是什么？为什么？
我在读这篇文章时已经假定,对于一个枢轴的明显选择是5或6,因为它位于列表的中间.我认为快速排序可以工作,因为我们每次都选择一个新的数据透视表.这使得后续问题更有意义,但是有没有人有正式的定义？
为什么最佳枢轴不实用？
最佳枢轴是您当前正在处理的集合的中位数,因为它会将集合拆分为两个大小相等的子集,从而保证O(n log n)性能.它不实用的原因是因为找到实际中位数的成本.你基本上必须对数据进行排序以找到中位数,所以它就像书Catch 22 - "我如何对数据进行排序？" "找到中位数""我如何找到中位数？" "排序数据".