Quicksort - 故障确定枢轴

我想了解快速排序，我得到的一般想法，但我遇到了以下问题的麻烦。是否有一种简单的方法可以在每次迭代后根据数组来确定使用哪个数据透视表？Quicksort - 故障确定枢轴

Consider the following array and its state after iterations of QuickSort on the array: 

Initial Array: 32, 12, 17, 73, 40, 88, 16, 75 
After Iter 1: 32, 12, 17, 40, 16, 73, 88, 75 
After Iter 2: 12, 16, 17, 40, 32, 73, 88, 75 
After Iter 3: 12, 16, 17, 40, 32, 73, 88, 75 
After Iter 4: 12, 16, 17, 32, 40, 73, 88, 75 
After Iter 5: 12, 16, 17, 32, 40, 73, 75, 88

命名此QuickSort执行中使用的数据透视选择策略。

提示：检查在每个阶段选择哪个值作为关键点。记住 QuickSort首先在之前对左子阵列及其左子阵列进行递归排序，然后对右子阵列进行排序。

来源

2012-10-31 Dawson

它正在使用选择中间值的最具成本效益的解决方案。这很容易选择，并且在数据已经排序（或大部分排序）时效率很高。 – paddy

选择任何元素作为主点，然后在第一次迭代中，所有小于主点的元素都放置在主点的左侧，并且如果它们已经不在主点的右侧，则向右更大。这意味着如果需要，也可以在数组中向前交换枢轴。了解这一点并观察迭代应该有助于确定关键点。

例如，在你上面的例子中，我相信中间元素被选为pivot，即73.在第一次迭代之后，所有比它小的元素被移动到左边，并且大于它被移动到正确的位置。

来源

2012-10-31 07:09:39 fayyazkl

谢谢，这就是我一直在寻找的。 – Dawson

欢迎您。请记住，这只是选择枢轴的方式之一。一般意图是理想的是总是将数组分成两半。如果它主要是这样，那么我们实现（nlogn）平均案例时间。如果不是，我们可能会遇到最坏的情况。 – fayyazkl

Quicksort - 故障确定枢轴

回答

相关问题