c++ - 这个特定用例的一个很好的排序算法

Question

struct Object {
    int16_t order = 0;
};

我有一个对象实例的 std::list，我想根据“顺序”成员变量对其进行排序。

• 较小的订单值放在列表的前面。
• 在循环时，如果当前订单值与现有订单值相同，我认为它应该放在现有订单之前，这样我就不必继续查看列表的其余元素。
• 列表最多可以包含 1024 个项目。

我正在寻找一种算法，它可以让我在最少的迭代次数或接近次数的情况下对列表进行排序。我现在采用的一种天真的方法会导致三角形数量的迭代，对于 1024 是: (1024(1024 + 1))/2 = 524,288

Answer 1

使用成员排序方法 - std::list::sort使用适当的比较器:

int main() {
    std::list<Object> objects{
        Object{4}, Object{2}, Object{6}, Object{7}, Object{42}
    };

    objects.sort([](const auto& lhs, const auto& rhs) {
        return lhs.order < rhs.order;
    });
}