相同结果：qsort与std::sort的比较

Question

请原谅信息的简洁。

我有一个记录数组。我想按照其中一个键的降序对其进行排序。记录的键不是唯一的。

qsort的比较函数：

int cmp(const record* rec1, const record* rec2) 
{
    return rec2->key - rec1->key;
}

std::sort的比较函数：

bool operator()(const record& rec1, const record& rec2) 
{
    return rec1.key > rec2.key;
}

这两个版本会产生相同的结果吗？当键相等时，我不确定sort/qsort是否表现相同。

- user3689963

---

“record”类型的定义是什么？ - user2100815

结构体 s { char* name; int key}; - user3689963

翻译以下与编程有关的内容，从英文到中文。仅返回翻译的文本：结果不能保证相等（由于未指定等价项的顺序），但两个范围都将被排序。 - Jarod42

是的，就像@Jarod42所提到的那样，快速排序一般情况下不是稳定排序。 - erip

我知道这并不是保证。我正在使用gcc。你知道内部情况吗？ - user3689963

@user3689963 - 根据qsort和std::sort之间的几个潜在差异，相同键的结果将有所不同：触发切换到堆排序和/或插入排序的条件；如何选择枢轴值；是否使用2路还是3路（第三个分区将是键==枢轴键），... - rcgldr

Answer 1

不能保证。

std::qsort:

如果comp指示两个元素相等，则它们的顺序未指定。

std::sort:

不能保证相等元素的顺序被保留。

如果需要保留相等元素的顺序，您需要使用稳定的排序算法。 std::stable_sort 是稳定的。

或者只需添加更多键以排序，以确保没有元素比较相等。

- nwp

Answer 2

不是这两种排序都能保证是稳定排序。使用任一排序算法，比较相等的元素可能不会以相同的顺序出现。

此外，在[alg.sort]中也没有保证它们使用相同的算法/算法实现。事实上，自C++11以来，std::sort已经保证是O（n log n），而尽管其名称为std::qsort，但它甚至不能保证是快速排序，更不用说具有任何特定的时间复杂度了（这意味着Bogosort是符合qsort实现的）。

编辑

由于在评论中您指定正在使用GCC并且是否感兴趣该平台是否使用相同的排序方式，答案仍然是“否”。

对于std::sort，它是“Introsort”（内省排序）（有关详细信息，请参见https://dev59.com/Omw05IYBdhLWcg3weBvu）。

对于qsort，它来自您的版本的GCC使用的libc。

- AndyG