2

有没有办法通过多个条件进行快速排序？例如，我有一组边。每条边都有源、目的地和长度。我想首先将长度较小的边缘放在我的数组中。但如果长度相同，我想用较小的源顶点对其进行排序。如果这些源顶点相同，我想按两个目标顶点中较小的一个进行排序。

例如：

4（源） 2（目的地） 3（长度）

1（源） 5（目的地） 3（长度）

由于它们都具有相同的长度，因此我们查看源顶点。由于第二条边小于第一条边，我们交换它们，因为我们按源顶点进行比较。

下面是我的快速排序，老实说，我不确定为什么它不能正确排序。如果有一种方法可以降低快速排序的效率但更稳定，我很乐意接受建议！

void quickSort(edge *e, int left, int right)
{
  int i = left, j = right;
  int temp, temp1, temp2;
  int pivot = (left + right)/2;
  while(i <= j)
  {
    while(e[i] < e[pivot])
      i++;
    while(e[pivot] < e[j])
      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);
}

我的条件排序：

bool edge::operator<(const edge &other) const 
{
    if (length < other.length)
        return true;
     else if ((length == other.length) && (source < other.source))
        return true;
     else if((length == other.length) && (source == other.source) && (destination < other.destination))
        return true;
     return false;
}

同样，如果有人知道如何通过降低时间复杂度但使其稳定来正确地进行快速排序，我很乐意接受任何建议！谢谢！有什么帮助吗？

编辑：这就是我调用快速排序的方式。我根据读取的边数调用它。

    quickSort(e, 0, edges-1); //-1 because if you put in edges, it'd go past the bounds of the array

编辑：当我尝试在我的算法中加入这样的东西时：

0 1 1

0 3 1

1 3 1

2 5 1

4 10 1

4 8 1

10 8 1

11 6 2

11 7 2

6 7 1

9 6 1

9 7 1

这是输出：

0 1 1

0 3 1

1 3 1

2 5 1

4 8 1

4 10 1

6 7 1

6 9 1

8 10 1 <- 应低于 7 9 1

7 9 1 <- 应该高于 8 10 1

6 11 2

7 11 2

4

2 回答 2

1

这样写更干净

if (length != other.length)
   return length<other.length;

if ( source != other.source)
   return source < other.source;

return destination < other.destination;

因为成员都是整数，所以你也应该能够做temp = e[i]等等。

这（以及您提交的代码）应该完成您想要的任务。

如果您遇到稳定性问题，那是因为快速排序不稳定。您可以通过添加更多条件来解决它，这样就lhs==rhs不会发生这种情况。或者，您可以尝试合并排序

坦率地说，我对快速排序没有太多经验，但是您的 impl 看起来确实与Wikipedias In Place Algorithm明显不同。例如，您的枢轴根本没有移动。你能检查一下是不是这个问题吗？

编辑

看了你的链接后

看起来链接的算法也使用枢轴作为值而不是索引（就像你一样）。在您认为您的枢轴值可能会移动之前，它看起来与您的语法相同，之后您的枢轴索引将指向其他东西

int pivot = arr[(left + right) / 2];

这有帮助吗？

于 2012-11-19T01:19:30.507 回答
0

编辑：这是就地快速排序的伪代码：http ://en.wikipedia.org/wiki/Quicksort#In-place_version

这与您的代码不同，因为枢轴是一个值（左右值的平均值）而不是索引。

如果您正在寻找一个简单的非最优解决方案，请按目标顶点对整个列表进行合并排序，然后按原点对整个列表进行合并排序，然后按边长对整个列表进行合并排序。这利用了合并排序是一种稳定的排序算法并且在边数上具有运行时间 O(E) 的事实。

于 2012-11-19T01:24:46.130 回答