编程论坛 → 数据结构与算法

快速排序算法的疑问

bubble_soup 发布于 2018-04-08 21:12， 2256 次点击

快速排序的pivot怎么选取？
据说是三数中值法。
那第一个pivot应该选最左边、最右边、还是中间的那个数字呢？

另外，pivot的选取为什么不能每次都选中间下标对应的那个值呢？这样不就可以避免分歧了吗？？？

4 回复

bubble_soup2018-04-08 21:13

请大家踊跃发言。有想法都可以说说看。

bubble_soup2018-04-08 21:13

请大家踊跃发言。有想法都可以说说看。

bubble_soup2018-04-08 21:18

pivot的选取，按照网上的版本最好的还是使用三数中值法。但是为什么不能使用中间下标法（我取的名字）呢？每次都取中间的那个数（整个数据集合的中间下标对应的值）为pivot呢，这样也不会一起歧义/

请大师指点2018-09-20 18:32

它的思路大概是这样的（我用我理解的方式说哈）：首先引入两个标签 I，J 分别标记数组的第一个和最后一个位置的元素；（2）我们把第一个位置的元素拿出来和J标记的元素比较，假如J标记的元素比拿出来的元素大呢，J就向前移（即：J－1），假如J标记的元素比拿出来的元素小呢，J所标记的元素就去取代刚刚空出来的位置。