1

我有一个对象，其中包含三个变量：源顶点、目标顶点和长度。我有一个快速排序算法，可以按对象的长度对对象进行排序。但是，我想要这样，如果我比较两个对象并且它们的长度相等，那么我的快速排序会将具有较小源顶点的对象排在具有较大源顶点的对象之前。如果它们也相等，我想比较目标顶点。我想用较小的源顶点对较大的目标顶点进行排序。这一切都将在一个数组中完成。下面是我的快速排序实现。请注意， 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);

}

如果长度相等，可能有人知道如何/在哪里执行顶点的排序？谢谢！

4

2 回答 2

2

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 语句以及临时变量的长序列（且容易出错）。

于 2012-11-13T07:15:38.680 回答
0

您需要创建一个比较函数并调用它，而不是比较长度。您没有pivot在代码中定义任何地方，但我认为它与getLength(). 您将需要更改pivot以使其成为索引。然后，你写：

while (compareEdge(e[i], e[pivot]) < 0)
    i++;
while (compareEdge(e[j], e[pivot]) > 0)
    j--;

您的compareEdge函数将比较长度。如果它们相等，那么它会按照您的描述比较顶点。

于 2012-11-13T07:16:12.083 回答