代码之家  ›  专栏  ›  技术社区  ›  Rick Jim DeLaHunt

stable_sort()是否还保留不相等元素的顺序?

c++
  •  -1
  • Rick Jim DeLaHunt  · 技术社区  · 7 年前

    cppreference 我知道这是为了 stable_sort 以下内容:

    均等元素的次序是可以保证的。

    我也读过这个问题 What is stability in sorting algorithms and why is it important? 了解 稳定性 .

    以下是我如何理解稳定排序:
    假设我有无序的航班 出发时间 目的地 .

    首先,我按时间排序。就像是

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

    然后按目标进行稳定排序。就像是

     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++底漆 似乎表明 稳定型 同时保证之前的订单 不相等元素 (如果是,则表示 稳定型 保留所有原始订单)。

    样本代码:

    #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;
    } 
    

    这里的文字让我怀疑 稳定型 保持所有原始元素的顺序。

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

    在第一次排序和擦除之后,我有:
    fox jumps over quick red slow the turtles

    经过稳定排序,我有:
    狐狸红过慢跳快龟


    所以我的问题是:

    用于 稳定型 ,只需查看前3个元素:

    fox red the ,这个订单是固定的吗?或者这只是其中一个可能的顺序:

    福克斯红 fox the red the red fox the fox red ……(6个结果)

    我是说,文件 只有 稳定型 保持的原始顺序 相等元素 . 福克斯红 不相等。他们有秩序。但从引用的文本和输出来看,似乎表明 它只是保持所有原始的秩序 .

    我是误解了什么,还是这里的教科书有问题,结果正好是按照之前的排序顺序输出的?

    2 回复  |  直到 7 年前
        1
  •  3
  •   The Dark    7 年前

    fox ,请 red ,和 the stable_sort .你所说的cppreference链接:

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

    所以,是的 fox red the 对于您的示例,顺序是固定的,因为稳定排序不会改变这三个(同样短)项目的相对顺序。

        2
  •  2
  •   aschepler    7 年前

    更准确地说 相等的 保证保存元素。或者更确切地说, stable_sort 保留元素的顺序,这些元素与用于排序的排序比较是等效的。

    像许多标准算法一样, std::stable_sort 要求使用比较方法对范围内的元素进行严格的弱排序。这两个版本都是正确的 operator< 对于使用 Compare 对象。严格弱序定义的一部分是由 !(x<y || y<x) !(comp(x,y) || comp(y,x)) 是等价关系。

    所以在第一个例子中,您的两个元素是 [A,1] [A,4] .在按目的地进行稳定排序的上下文中,假设您的比较函数将为这两者返回false comp([A,1], [A,4]) comp([A,4], [A,1]) ,因此元素是等效的。但我们可以说,他们不平等,在某种意义上,他们是不相同的。(注:这完全独立于 operator== operator!= 元素类型的函数,如果这样的东西甚至被定义了。)

    在单词排序示例中, "fox" "red" 相当于 isShorter ,因为 isShorter("fox", "red") isShorter("red", "fox") 都是假的。所以 稳定型 呼叫使用 必须保留这样一个事实 “狐狸” 先于 “红色” .但是,这两个词显然是不相同的。是的,命令 fox red the 是固定的,因为排序必须保留来自同一等价类的所有这些单词的相对顺序。另一方面, “红色” "jumps" 不是等价的,因为 isShorter("red", "jumps") 是真的,所以排序需要交换订单,以便 “红色” 在某个地方比 “跳跃” .

    实际上,对于任何范围和有效的严格弱序比较,只有一个允许的结果 STD::稳定排序 (不像 std::sort 如果对序列中的每个等价类元素进行任何重新排序,这是正确的)。