如何使用额外的 O(n) space 实现稳定的快速排序算法？

Question

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

Answer 1

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

然后在比较中，如果两个元素相等，也比较它们的索引，这样就稳定了。

Answer 2

按照 Blindy 和 R 的建议，您可以只对索引进行排序，然后可以使用循环排序的变体对原始数组进行就地排序，副作用是排序后的索引将重新排列回0 到 n-1。每一步都放置一个元素，所以时间复杂度为O(n)。

void reorder_according_to(int array[], size_t indices[], size_t len)  
{
size_t i, j, k;
int t;
    for(i = 0; i < len; i++){
        if(i != indices[i]){
            t = array[i];
            k = i;
            while(i != (j = indices[k])){
                array[k] = array[j];
                indices[k] = k;
                k = j;
            }
            array[k] = t;
            indices[k] = k;
        }
    }
}

如何使用额外的 O(n) space 实现稳定的快速排序算法？

How can I implement a stable quicksort algorithm using O(n) additional space?

c

sorting

algorithm

quicksort

stable-sort