如何在维护主要排序的同时执行辅助排序

Question

例如,我正在编写带有条目的哈希表(字符串键,int计数).首先,我正在进行选择排序,按计数对每个条目进行排序.然后我想按字母顺序对它们进行排序,同时保持排序的计数.有没有办法做到这一点？

这是主要的排序.

void MyTrends::sortByCount(Entry* arr, int sizeOfArray) {
  int maxIndex; // the index of the element that has the highest count
  for(int i=0; i < sizeOfArray-1; i++){
      maxIndex = i;
      for(int j=i+1; j < m; j++){
          if(arr[j].getCount() > arr[maxIndex].getCount()){ //if the count of element j is higher than the count of the Entry at the current max index then change the max index to j
              maxIndex = j;
          }
      }
      if (maxIndex != i) {
          Entry temp = arr[i]; //next 2 lines + this line are swapping max to first position and old first position to the position the max was in
          arr[i] = arr[maxIndex];
          arr[maxIndex] = temp;
      }
  }
}

编辑:在考虑了一些之后,这可以通过首先按字母顺序排序然后使用稳定排序按计数排序来完成吗？

Answer 1

您需要的是自定义Entry比较运算符.例如

struct Entry {
    int num;
    char letter;
}

bool operator< (const Entry& lhs, const Entry& rhs)
{
    if ( lhs.num == rhs.num )
        return lhs.letter < rhs.letter;
    else
        return lhs.num < rhs.num;
}

然后使用自定义比较对其进行排序.该列表将首先按数字(num成员)排序,然后按字母顺序使用该letter成员.

Answer 2

struct Entry {
  int num;
  char letter;
  friend auto make_tie(Entry const&e){
    return std::tie(e.num,e.letter);
  }
  friend bool operator<(Entry const&lhs, Entry const& rhs){
    return make_tie(lhs)<make_tie(rhs);
  }
};

这利用了tuple的字典排序来对您的条目进行排序。 tie制作一个引用元组。

它需要编写make_tie，但是一旦你拥有了它，你就可以== <免费获得它，并且你还可以将它用于其他一些功能——序列化、打印swap等。

make_tie是 C++14 - 对于 C++11，您需要在和of->decltype(std::tie(e.num,e.letter))之间添加。){make_tie