c++ - 使 QuickSort 按多个条件排序？

Question

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

例如:

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

Answer 1

这样写比较干净

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

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

return destination < other.destination;

您还应该能够执行 temp = e[i] 等操作，因为成员都是整数。

我认为这(以及您提交的代码)应该可以完成您想要的任务。

如果您遇到稳定性问题，那是因为 quicksort isnt stable .您可以通过添加更多条件来绕过它，这样 lhs==rhs 就不会发生。或者你可以尝试 Mergesort

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

---

编辑

看了your link之后

看起来链接的算法也使用 pivot 作为值而不是索引(就像你所做的那样)。它在语法上看起来与你的相同，直到你认为你的枢轴值可能会移动，之后你的枢轴索引将指向其他东西

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

这有帮助吗？