1

我试图理解快速排序，我得到了一般的想法，但我在下面的问题上遇到了麻烦。有没有一种简单的方法可以在每次迭代后根据数组来识别正在使用哪个枢轴？

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

命名此快速排序执行中使用的枢轴选择策略。

提示：检查在每个阶段选择什么值作为枢轴。请记住，快速排序首先对左子数组及其左子数组进行递归排序，然后再对右子数组进行排序。

4

1 回答 1

1

选择任何元素作为枢轴，然后在第一次迭代中，所有小于枢轴的元素都放在枢轴的左侧，如果它们已经不是，则放在右侧。这意味着如果需要，也可以在阵列中提前交换枢轴。了解这一点并查看迭代应该有助于确定枢轴。

例如，在您的上述情况下，我相信中间元素被选为枢轴，即 73。第一次迭代后，所有小于它的元素都被移动到左边，大于它的元素都被移动到右边。

于 2012-10-31T07:09:39.483 回答