C++ std::sort 和 std::stable_sort 有什么区别？

What is the difference between std::sort and std::stable_sort?

提问by user3603858

I would like to know how std::sort and std::stable_sort differ with respect to functionality, memory and hardware? The documentationmentions that "Sorts the elements in the range [first,last) into ascending order, like sort, but stable_sort preserves the relative order of the elements with equivalent values.", but that didn't make sense to me. What is the "relative order" and "equivalent values"?

我想知道 std::sort 和 std::stable_sort 在功能、内存和硬件方面有何不同？该文件提到，“在排序范围[第一要素，最后一个）按升序进行排序一样，但是stable_sort蜜饯具有同等数值的元素的相对顺序。”，但没有任何意义，我。什么是“相对顺序”和“等效值”？

回答by Lightness Races in Orbit

Yes, it's as you said, and this is not a concept unique to C++.

是的，正如你所说，这不是C++独有的概念。

Stable sorts preserve the physical order of semantically equivalent values.

稳定排序保留语义等效值的物理顺序。

---

---

std::sort:

std::sort：

The order of equal elements is not guaranteed to be preserved.
Complexity:O(N·log(N)), where N= std::distance(first, last)comparisons

不保证相等元素的顺序会被保留。
复杂性：O(N·log(N))，其中N=std::distance(first, last)比较

std::stable_sort:

std::stable_sort：

The order of equal elements is guaranteed to be preserved.
Complexity:O(N·log^2(N)), where N= std::distance(first, last)applications of cmp. If additional memory is available, then the complexity is O(N·log(N)).

保证相等元素的顺序被保留。
复杂性：O(N·log^2(N))，其中N= 的std::distance(first, last)应用cmp。如果有额外的内存可用，则复杂度为O(N·log(N))。

The implication is that std::stable_sortcannot be performed quite as efficiently in terms of execution time, unless "additional memory is available" in which case it is not being performed as efficiently in terms of memory consumption.

这意味着std::stable_sort不能在执行时间方面非常有效地执行，除非“有额外的内存可用”，在这种情况下，它在内存消耗方面的执行效率不高。

回答by rcgldr

As mentioned, the standard only notes that std::stable_sort preserves the original order for equal elements, while std::sort doesn't.

如前所述，该标准仅指出 std::stable_sort 保留了相等元素的原始顺序，而 std::sort 则没有。

In the case of HP / Microsoft STL, std::sort is usually quick sort, unless the nesting gets too deep, in which case it switched to heap sort. Quick sort time complexity is typically O(n log(n)), but it's worst case is O(n^2), which is avoided with the switch to heap sort, since heap sort is always O(n log(n)) (but slower than quick sort so it's only used to avoid O(n^2)).

在 HP / Microsoft STL 的情况下，std::sort 通常是快速排序，除非嵌套太深，在这种情况下它切换到堆排序。快速排序的时间复杂度通常为 O(n log(n))，但最坏的情况是 O(n^2)，切换到堆排序可以避免这种情况，因为堆排序始终为 O(n log(n)) （但比快速排序慢，因此它仅用于避免 O(n^2)）。

In the case of HP / Microsoft STL, std::stable_sort is a hybrid bottom up merge sort, using insertion sort to create sorted groups of 32 elements, then doing bottom up merge sort with the groups. The array (or vector) is split into two, a temporary array (or vector) 1/2 the size of the array to be sorted is allocated, and used to do a merge sort for both halfs of the array. Then one of the half arrays is moved to the temp array to do a final merge pass. Merge sort is also O(n log n), taking a bit longer for sorting arrays of objects, but merge sort is often faster if sorting an array of pointers to objects where a comparison function is included in the call. This because merge sort involves more moves but fewer compares than quick sort.

在 HP / Microsoft STL 的情况下，std::stable_sort 是一种混合自底向上归并排序，使用插入排序创建 32 个元素的排序组，然后对这些组进行自底向上归并排序。将数组（或向量）一分为二，分配一个1/2的待排序数组大小的临时数组（或向量），用于对数组的两半进行归并排序。然后将半个数组之一移动到临时数组以执行最终合并传递。合并排序也是 O(n log n)，对对象数组进行排序需要更长的时间，但是如果对指向对象的指针数组进行排序，其中调用中包含比较函数，则合并排序通常会更快。这是因为合并排序比快速排序涉及更多的移动但更少的比较。

For sorting an array of integers, a radix sort is faster. If sorting by byte, then it takes 4 passes to sort an array of 32 bit integers, and 8 passes to sort an array of 64 bit integers.

对于整数数组的排序，基数排序更快。如果按字节排序，则对 32 位整数数组进行排序需要 4 遍，对 64 位整数数组进行排序需要 8 遍。

回答by Dietmar Kühl

As you correctly realized, std::stable_sort()retains the relative order of objects considered equivalent. std::sort()doesn't have this requirement. As a result, std::stable_sort()is likely to be more resource-hungry: it will probably be slower and will probably use more temporary memory as it has to obey more constraints. I'm not aware of any algorithm which does in-place stable sorting as efficient as sorting.

正如您正确意识到的那样，std::stable_sort()保留被视为等效的对象的相对顺序。std::sort()没有这个要求。因此，std::stable_sort()它可能更需要资源：它可能会更慢，并且可能会使用更多的临时内存，因为它必须遵守更多的约束。我不知道有任何算法可以像排序一样有效地进行就地稳定排序。