如何使用O（n）额外空间实现稳定的快速排序算法？

本文介绍了如何使用O（n）额外空间实现稳定的快速排序算法？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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.