如何使用O（n）额外空间实现稳定的快速排序算法？ [英] How can I implement a stable quicksort algorithm using O(n) additional space?

问题描述

与一般的快速排序算法不同，我可以使用额外的数组来执行稳定的快速排序。我知道如何随机选择枢轴并相应地进行分区，但是我无法弄清楚如何利用附加数组来使其稳定。

I am allowed to use an extra array to perform a stable quicksort unlike the general quicksort algorithm. I know how to select the pivot at random and partition accordingly but I'm not able to figure out how to make use of the additional array to make it stable.

推荐答案

想到的最简单的方法是将初始索引存储在数组（1、2、3等）中，并在交换数据时四处交换它们。

The most trivial way that comes to mind is to store the initial indices in the array (1, 2, 3, etc) and swap them around as you swap the data.

然后在比较中，如果两个元素相等，则也比较它们的索引，从而使其稳定。

Then in the comparison, if the two elements are equal, compare their indices too, thus making it stable.

这篇关于如何使用O（n）额外空间实现稳定的快速排序算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！