3 
class Foo
{
    public:
        int num;
        int other;
};

int main()
{
    Foo bar[10].num = {1, 9, 3, 5, 1, 6, 10, 0, 6, 3};

    //quicksort(bar)

    return 0;
}

我想编写一个快速排序函数，按“num”升序对“bar”数组进行排序。不太确定什么是最好的方法，因为我从来没有写过快速排序。我查看了一些示例代码，但我看不到如何针对这种情况修改它们。通过将指针传递给数组的第一个和最后一个元素来完成的就地排序不起作用，因为这只会对“num”成员进行排序，而不是对整个对象进行排序。将对象数组拆分为一个较低的数组、一个枢轴和一个较高的数组并递归排序每个看起来很有希望，但我不确定传递值将如何工作......

非常感谢任何帮助。抱歉，如果之前有人问过这个问题。

4

4 回答 4

11

首先，您编写一个函数（或仿函数）来比较您想要的任何值的对象。它应该接受两个对象并返回一个布尔值。如果第一个应该在第二个之前，它应该返回 true，否则返回 false。然后将其传递给 std::sort。

struct compare_Foo_by_num
{
    bool operator() (const Foo & lhs, const Foo & rhs) { return lhs.num < rhs.num; }
};

int main()
{
    Foo bar[10];

    std::sort(bar, bar+10, compare_Foo_by_num());
}
于 2011-01-02T18:19:41.680 回答
3

您可以重载operator<以比较所需的成员，然后使用std::sort.

#include <algorithm>

class Foo
{
public:
    int num;
    int other;
};

bool operator<(const Foo& x, const Foo& y)
{
    return x.num < y.num;
}

int main()
{
    Foo bar[10] = {{1, 5}, {9, 2}, {3, 0}, {5, 7}, {1, 3}, {6, 4}, {10, 8}, {0, 9}, {6, 2}, {3, 5}};
    std::sort(bar + 0, bar + 10);
}

请注意，您需要两个数字来初始化 a Foo，而不仅仅是您在排序时感兴趣的那个。

如果您不能或不想重载operator<for Foo，其他选项包括将良好的旧 C 风格函数指针或 C++ 风格函数对象作为第三个参数传递给std::sort.

于 2011-01-02T18:19:56.743 回答
1

另一种选择是将 std::sort 与 lambda 表达式一起使用：

int main()
{
    Foo bar[10] = {{1,5},{9,2},{3,0},{5,7},{1,3},{6,4},{10,8},{0,9},{6,2},{3,5}};

    std::sort(bar, bar + 10, [](const Foo &x, const Foo &y) {
        return x.num < y.num;
    });
}
于 2011-01-02T19:15:28.730 回答
0

如果您坚持实现自己的快速排序，我建议您观看此视频以帮助您更好地可视化算法。尽管您从未编写过快速排序，但在观看之后您可能会发现它更容易实现。 http://www.youtube.com/watch?v=vxENKlcs2Tw

于 2011-01-02T18:19:08.697 回答