c++ - 提出了一种对大型对象数组进行排序的算法；谁能告诉我这个算法叫什么？ (在谷歌上找不到)

Question

我需要对大型对象数组进行排序，这让我开始思考:有没有一种方法可以最大限度地减少交换次数？

所以我使用快速排序(但任何其他快速排序也应该在这里工作)将 索引 排序为数组中的元素；指数的交换成本低廉。然后我使用这些索引将实际对象交换到它们的位置。不幸的是，这使用 O(n) 额外空间来存储索引。下面的代码说明了该算法(我称之为 IndexSort)，并且在我的测试中，对于大型对象数组，它似乎比普通快速排序更快。

template <class Itr>
void IndexSort(Itr begin, Itr end)
{
    const size_t count = end - begin;

    // Create indices
    vector<size_t> ind(count);
    iota(ind.begin(), ind.end(), 0);

    // Sort indices
    sort(ind.begin(), ind.end(), [&begin] (const size_t i, const size_t j)
    {
        return begin[i] < begin[j];
    });

    // Create indices to indices. This provides
    // constant time search in the next step.
    vector<size_t> ind2(count);
    for(size_t i = 0; i < count; ++i)
        ind2[ind[i]] = i;

    // Swap the objects into their final places
    for(size_t i = 0; i < count; ++i)
    {
        if( ind[i] == i )
            continue;

        swap(begin[i], begin[ind[i]]);

        const size_t j = ind[i];

        swap(ind[i], ind[ind2[i]]);
        swap(ind2[i], ind2[j]);
    }
}

现在我测量了快速排序和索引排序完成的(大型对象的)交换，发现快速排序执行的交换次数要多得多。所以我知道为什么 IndexSort 可以更快。

但是任何具有更多学术背景的人都可以解释为什么/这个算法实际上是如何工作的吗？ (这对我来说并不直观，尽管我不知何故想到了它)。

谢谢!

编辑:下面的代码用于验证IndexSort的结果

// A class whose objects will be large
struct A
{
    int id;
    char data[1024];

    // Use the id to compare less than ordering (for simplicity)
    bool operator < (const A &other) const
    {
        return id < other.id;
    }

    // Copy assign all data from another object
    void operator = (const A &other)
    {
        memcpy(this, &other, sizeof(A));
    }
};

int main()
{
    const size_t arrSize = 1000000;

    // Create an array of objects to be sorted
    vector<A> randArray(arrSize);
    for( auto &item: randArray )
        item.id = rand();

    // arr1 will be sorted using quicksort
    vector<A> arr1(arrSize);
    copy(randArray.begin(), randArray.end(), arr1.begin());

    // arr2 will be sorted using IndexSort
    vector<A> arr2(arrSize);
    copy(randArray.begin(), randArray.end(), arr2.begin());

    {
        // Measure time for this
        sort(arr1.begin(), arr1.end());
    }

    {
        // Measure time for this
        IndexSort(arr2.begin(), arr2.end());
    }

    // Check if IndexSort yielded the same result as quicksort
    if( memcmp(arr1.data(), arr2.data(), sizeof(A) * arr1.size()) != 0 )
        cout << "sort failed" << endl;

    return 0;
}

编辑:使测试不那么病态；将大型对象类的大小减少到仅 1024 字节(加一个 int)，并将要排序的对象数量增加到一百万。这仍然导致索引排序明显快于快速排序。

编辑:这确实需要更多测试。但这让我想到，如果 std::sort 可以在编译时检查对象大小，并且(取决于某个大小阈值)选择现有的快速排序实现或此 IndexSort 实现，会怎样。

此外，IndexSort 可以描述为“就地标签排序”(参见 samgak's answer and my comments below)。

Answer 1

好像是一个tag sort :

For example, the popular recursive quicksort algorithm provides quite reasonable performance with adequate RAM, but due to the recursive way that it copies portions of the array it becomes much less practical when the array does not fit in RAM, because it may cause a number of slow copy or move operations to and from disk. In that scenario, another algorithm may be preferable even if it requires more total comparisons.

One way to work around this problem, which works well when complex records (such as in a relational database) are being sorted by a relatively small key field, is to create an index into the array and then sort the index, rather than the entire array. (A sorted version of the entire array can then be produced with one pass, reading from the index, but often even that is unnecessary, as having the sorted index is adequate.) Because the index is much smaller than the entire array, it may fit easily in memory where the entire array would not, effectively eliminating the disk-swapping problem. This procedure is sometimes called "tag sort".

如上所述，标签排序可用于对无法放入内存的大量数据进行排序。然而，即使它可以放入内存，它仍然需要较少的内存读写操作来处理大型对象数组，如您的解决方案所示，因为每次都不会复制整个对象。

实现细节:虽然您的实现仅对索引进行排序，并在进行比较时通过索引返回原始对象数组，但另一种实现方式是将索引/排序键对存储在排序缓冲区中，使用排序键进行比较。这意味着您可以进行排序，而无需立即将整个对象数组存储在内存中。

标记排序的一个例子是 LINQ to Objects .NET 中的排序算法:

The sort is somewhat flexible in that it lets you supply a comparison delegate. It does not, however, let you supply a swap delegate. That’s okay in many cases. However, if you’re sorting large structures (value types), or if you want to do an indirect sort (often referred to as a tag sort), a swap delegate is a very useful thing to have. The LINQ to Objects sorting algorithm, for example uses a tag sort internally. You can verify that by examining the source, which is available in the .NET Reference Source. Letting you pass a swap delegate would make the thing much more flexible.