如何根据 C++ 中的给定索引对列表进行就地排序

Question

我有一大堆对象（结构）。它们已经排序并且索引已保存在另一个列表中。如何根据索引进行就地排序？例如，

FOO A[5] =[a5,a4,a8,a1,a3]
int idx[5] = [3,0,4,1,2]

预期结果：

A[5] = [a1,a5,a3,a4,a8]

由于列表A非常大，需要一种无需额外大缓冲区的就地排序方法。我怎样才能意识到这一点？

谢谢大家

Answer 1

您正在寻找的是所谓的“应用排列”并且被认为是已解决的问题（幸运的是）。

Raymond 在他的博客上对此进行了有趣的讨论，并给出了一个就地解决方案 https://devblogs.microsoft.com/oldnewthing/20170102-00/?p=95095

我冒昧地调整了他的数组解决方案。您可以在他的博客中找到处理向量的原始版本。

#include <iostream>

template<typename T, size_t N>
void apply_permutation(T * v, size_t * indices)
{
    using std::swap; // to permit Koenig lookup
    for (size_t i = 0; i < N; i++) {
        auto current = i;
        while (i != indices[current]) {
            auto next = indices[current];
            swap(v[current], v[next]);
            indices[current] = current;
            current = next;
        }
        indices[current] = current;
    }
}

int main(){
    const int N = 5; 
    std::string data[N] = {"a5","a4","a8","a1","a3"};
    size_t idx[N] = {3,0,4,1,2};
    apply_permutation<std::string,N>(data, idx);

    for(auto & s : data){
        std::cout << s << std::endl;
    }
}

输出：

g++ test2.cpp && ./a.exe
a1
a5
a3
a4
a8

如何根据 C++ 中的给定索引对列表进行就地排序

How to do in-place sorting a list according to a given index in C++

c++

sorting

indexing

in-place