拓展排序的偏序匹配

在力扣OJ 15. 三数之和中，有这么一段代码：

  

   

    

     

    
    

     

      //给vector拓展，加上id并排序
     
    
   

    

     

    
    

     

      template<typename T>
     
    
   

    

     

    
    

     

      bool cmp(T x,T y)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    return x<y;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      template<typename T>
     
    
   

    

     

    
    

     

      vector<pair<T,int>> sortWithId(vector<T>v)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          vector<pair<T,int>>ans;
     
    
   

    

     

    
    

     

          ans.resize(v.size());
     
    
   

    

     

    
    

     
    for(int i=0;i<v.size();i++)ans[i].first=v[i],ans[i].second=i;
     
    
   

    

     

    
    

     
    sort(ans.begin(),ans.end(),[](pair<T,int>p1,pair<T,int>p2){return cmp(p1.first,p2.first);});
     
    
   

    

     

    
    

     
    return ans;      
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      //2个vector中寻找和为s的对，返回结果的每一行都是[id1,id2]
     
    
   

    

     

    
    

     

      template<typename T>
     
    
   

    

     

    
    

     

      vector<vector<int>> findSum(vector<T>v1,vector<T>v2,T s)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          vector<vector<int>>ans;
     
    
   

    

     

    
    

     
    int m=min(int(v1.size()*v2.size()),1234567);
     
    
   

    

     

    
    

     

          ans.reserve(m);
     
    
   

    

     

    
    

     

          vector<int>tmp(2);
     
    
   

    

     

    
    

     

          vector<pair<T,int>>v3=sortWithId(v2);
     
    
   

    

     

    
    

     
    sort(v2.begin(), v2.end(),cmp<T>);
     
    
   

    

     

    
    

     
    for(int i=0;i<v1.size();i++)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        auto it1=lower_bound(v2.begin(), v2.end(), s-v1[i]);
     
    
   

    

     

    
    

     
        auto it2=upper_bound(v2.begin(), v2.end(), s-v1[i]);
     
    
   

    

     

    
    

     

              tmp[0]=i;
     
    
   

    

     

    
    

     
        for(auto j=it1;j<it2;j++)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  tmp[1]=v3[j-v2.begin()].second;
     
    
   

    

     

    
    

     

                  ans.push_back(tmp);
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return ans;
     
    
   

    

     

    
    

     

      }
     
    
  
 

其中两次用到sort函数：

  

   

    

     

    
    

     

          vector<pair<T,int>>v3=sortWithId(v2);
     
    
   

    

     

    
    

     
    sort(v2.begin(), v2.end(),cmp<T>);
     
    
  
 

一个是带ID的拓展数据域的排序，一个是原朴素数据域的排序，然后根据相同的数组下标直接对应。

这么做有没有根据？

换句话说，拓展排序和原排序一定偏序匹配吗？

偏序匹配的条件有2个：

（1）排序算法不含随机行为，即无论调用多少次，它的行为都是完全一致的。

（2）比较函数对拓展封闭，即拓展数据域的比较逻辑和原比较逻辑完全一致。

总结：拓展排序有两种，一种是上面代码中所示，比较逻辑（即cmp函数）不变，拓展排序和原排序是偏序匹配的，

另外一种是利用ID实现把不稳定排序变成稳定排序，需要修改cmp函数，比较逻辑变了，这样的一个稳定排序的结果和原来的不稳定排序的结果自然也是不能确保偏序匹配的。当然，如果原排序就是稳定排序，那就和拓展排序是偏序匹配的。

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/107223702