时间戳

首页 > 解决方案 > stable_sort() 是否也保留不相等元素的顺序？

c++ - stable_sort() 是否也保留不相等元素的顺序？

问题描述

从cppreference，我知道stable_sort：

保证保持相等元素的顺序。

我也读了这个问题什么是排序算法的稳定性，为什么它很重要？了解稳定性的概念和基本用法。

以下是我对稳定排序的理解：
假设我有无序的航班起飞时间和目的地。

首先，我按时间排序。这就像

d-time dest
   1     A
   2     B
   3     C
   4     A
   5     B

然后按dest稳定排序。这就像

 dest   d-time
   A     1   (stable sort guarantee that [A,1] comes before [A,4])
   A     4
   B     2   (stable sort guarantee that [B,2] comes before [B,5])
   B     5
   C     3

但是一个示例C++ Primer似乎表明这stable_sort也保证了先前不相等元素的顺序（如果是这样，则意味着stable_sort保持所有原始顺序）。

示例代码：

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;

bool isShorter(const string &s1, const string &s2)
{
    return s1.size() < s2.size();
}

int main(int args, char *argv[])
{
    vector<string> words;
    string in_word;
    istringstream isin("the quick red fox jumps over slow turtles");
    while (isin >> in_word) {
        words.push_back(in_word);
    }
    sort(words.begin(), words.end());
    auto end_unique = unique(words.begin(), words.end());
    words.erase(end_unique, words.end());

    stable_sort(words.begin(), words.end(), isShorter);

    for (auto &s : words) {
        cout << s << " ";
    }
    cout << endl;
}

这里的文字让我质疑是否stable_sort保持所有原始元素的顺序。

假设words在此调用之前是按字母顺序（第一次排序和擦除函数调用），在调用之后，words将按元素大小排序，并且每个长度的单词保持字母顺序。如果我们在原始向量上运行此代码，输出将是
fox red the over slow jumps quick turtle

第一次排序和擦除后，我有：
fox jumps over quick red slow the turtles

稳定排序后，我有：
fox red the over slow jumps quick turtle

所以我的问题是：

对于stable_sort，只需查看前 3 个元素：

fox red the，这个顺序是固定的吗？或者这只是安排中的一种可能顺序：

fox red the fox the red the red fox the fox red ...（6 个结果）

我的意思是，文件只说保持相等元素stable_sort的原始顺序。不相等。他们有秩序。但是从引用的文本和输出来看，似乎表明它只是保持了所有原始顺序。fox red the

是我误解了什么还是教科书在这里错了，输出只是碰巧遵循了之前的排序顺序？

标签： c++

解决方案

fox, red, 和the就stable_sort. 您拥有的 cppreference 链接说：

使用给定的比较函数 comp 比较元素。

所以，是的fox red the，您的示例的顺序是固定的，因为 stable_sort 不会改变这三个（同样短的）项目的相对顺序。

推荐阅读