c++ - (C++) 为相等元素的快速排序添加随机性

Question

我使用以下代码对 std.vector 中的元素进行排序

struct element {
    int order;
    int someValue;
};

int comp( element a, element b ) {
    if (a.order < b.order)
        return true;
    return (rand() % 2) == 0;
}

vector.quickSort(comp);

如果我尝试在具有相同顺序值的元素上添加随机性，此代码是否正确

Answer 1

Is this code correct.

您确实应该使用一些数据编写一个测试来检查这一点。

---

如果您编写一个测试，您会发现一些错误并知道原因，如果我们查看一下

if (a.order < b.order)
    return true;
return (rand() % 2) == 0;

您可以看到缺少 a.order > b.order 案例，这就是为什么它不能正确地适用于该案例，我们可以通过这样做来修复此问题，而不是专注于特殊情况相反，并将其他两种情况保留为其默认行为(检查顺序):

if (a.order == b.order)
    return (rand() % 2) == 0;
else
    return a.order < b.order;