c++ - Quicksort 中相等值的比较

Question

我有一个包含三个变量的对象:源顶点、目标顶点和长度。我有一个按长度对对象进行排序的快速排序算法。但是，我想要这样，如果我比较两个对象并且它们的长度相等，那么我的快速排序会将具有较小源顶点的对象排在具有较大源顶点的对象之前。如果它们也相等，我想比较目标顶点。我想用较小的源顶点对较大的目标顶点进行排序。这一切都将在一个数组中完成。下面是我对快速排序的实现。请注意，e[i] 是我的对象，它包含我的顶点和长度。

void quickSort(edge *e, int left, int right)
{
  int i = left, j = right;
  int temp, temp1, temp2;
  while(i <= j)
  {
    while(e[i].getLength() < pivot)
      i++;
    while(e[j].getLength() > pivot)
      j--;
    if(i <= j)
    {
      temp = e[i].getLength();
      temp1 = e[i].getEdgeSrc();
      temp2 = e[i].getEdgeDes();
      e[i].setLength(e[j].getLength());
      e[i].setEdgeSrc(e[j].getEdgeSrc());
      e[i].setEdgeDes(e[j].getEdgeDes());
      e[j].setLength(temp);
      e[j].setEdgeSrc(temp1);
      e[j].setEdgeDes(temp2);
      i++;
      j--;
    } //if statement
  }///while loop
  if(left < j)
    quickSort(e, left, j);
  if(i < right)
    quickSort(e, i, right);

如果长度相等，有人知道如何/在何处执行顶点排序吗？谢谢!

Answer 1

最好为 edge 定义一个比较运算符执行您需要它执行的操作的对象:

class edge
{
  /* ... */
public:

  bool operator<(const edge &other) const
  {
     /* Length is first criterion: */
     if (length < other.length)
        return true;
     /* Source vertex is second criterion: */
     else if ((length == other.length) && (src < other.src))
        return true;
     return false;
  }

  /* ... */
};

然后，在您的快速排序实现中，您使用此运算符来比较 edge对象，而不是访问 getLength()等直接:

while(e[i].getLength() < pivot)
  i++;

成为

while(e[i] < pivot)
  i++;

和

while(e[j].getLength() > pivot)
  j--;

成为

while(pivot < e[j])
  j--;

请注意，我只定义了 operator< , 不是 operator> ，所以我建议只使用它。或者，您可以定义 operator>

请注意，上面我假设 pivot是对当前枢轴元素的引用。如果它实际上是当前数据透视表的整数索引，则需要将其替换为 e[pivot] .

---

单独说明:您可能想使用 std::swap(e[i],e[j]);而不是冗长(且容易出错)的 get 和 set 语句序列以及临时变量。