排序算法 - 方法

Question

我需要使用面向对象的方法来实现三种不同的排序算法，我一直在思考最好的方法来解决这个问题。

基本上，我认为应该是这样的：

-> 排序（类、接口、多态）

继承：

-> 冒泡排序

-> 插入排序

-> 快速排序

如果每个排序都有相同的接口，那么访问不同的排序方法会更容易，这意味着当我想要添加其他排序算法时，我可以轻松地将它们实现到当前的设计和类结构中。

我的问题是：

• 这是否是一个好的方法？

• 是否可以使用模板？例如，如果我想使用冒泡，它会调用冒泡排序，如果我想使用插入，它会调用插入排序？

- Phorce

Answer 1

Sort应该是一个接口或抽象类，而冒泡/插入/快速排序应该是实现/具体类。

另外值得学习以下内容：

策略模式：

http://en.wikipedia.org/wiki/Strategy_pattern

以及

状态模式：

http://en.wikipedia.org/wiki/State_pattern

至于模板，在你的情况下我认为不值得使用。

- sampson-chen

Answer 2

建议使用接口（纯虚类）

接口方法：

class sort_algorithm_interface {
public:
    virtual void sort(std::vector<int>& input) const  = 0;
};

class BubbleSort : public sort_algorithm_interface {
public:
    virtual void sort(std::vector<int>& input) const {/* sort the input */}
};

class InsertionSort: public sort_algorithm_interface {
public:
    virtual void sort(std::vector<int>& input) const {/* sort the input */}
};

class QuickSort: public sort_algorithm_interface {
public:
    virtual void sort(std::vector<int>& input) const {/* sort the input */}
};

现在，当您想要进行排序时，请按照以下步骤操作：

sort_algorithm_interface& s = QuickSort(input);
s.sort(input);

模板方法：

class BubbleSort  {
public:
    void sort(std::vector<int>& input) const {/* sort the input */}
};

class InsertionSort {
public:
    void sort(std::vector<int>& input) const {/* sort the input */}
};

class QuickSort {
public:
    void sort(std::vector<int>& input) const {/* sort the input */}
};

template<typename Sort>
class MySort {
    void sort(std::vector<int>& input) {
        Sort s;
        s.sort(begin, end);
    }
}

这是如何使用的：

使用方法如下:

MySort<QuickSort> s;
s.sort(input);

- andre

---

谢谢 :)！那么对于模板方法，冒泡排序等等...仍然会继承自Sort吗？ - Phorce

只是想澄清一下，我可以在不创建抽象类的情况下实现“模板方法”吗？ - Phorce

@Phorce 模板方法中没有继承。只需为冒泡排序实现排序函数，MySort<BubbleSort> s; s.sort 将使用冒泡排序对您的数据进行排序； - andre

@Phorce 是的，你可以使用模板方法而不需要抽象类。 - andre

@Phorce 模板方法对我来说更清晰一些。但这只是个人选择。这取决于你的偏好。 - andre

Answer 3

在C++中正确的做法是使用模板。

对某些东西进行排序是一种算法，通常没有或仅有很少的持久状态。排序不是一个对象 - 它是数据上的函数（可能是对象）。

std库已经有了一个带有以下签名的排序函数：

template<typename I, typename C = std::less<typename std::iterator_traits<I>::value_type> >
void sort(I begin, I end, C comp = C());

迭代器begin和end表示要排序的值范围，而comp是一个函数对象（或函数），当传递值范围内的两个元素时，告诉你第一个元素是否小于第二个元素。

要在std::vector上使用这个函数，您可以像这样操作：

std::vector<int> myVector; // assume it has some data in it
sort( myVector.begin(), myVector.end() );

std::sort通常是快速排序。但其接口适用于快速排序、冒泡排序和插入排序。这种方法的一个重要优点是可以互相调用排序算法。例如，虽然在大数据集下快速排序更快，但在小数据集下插入排序的简单性胜出（较低的常数因子，即使有n^2的开销）。因此，通过编写这样的排序方式，快速排序递归调用在元素数量较小时可以变为插入排序。

现在，如果需要在运行时替换使用的算法，则需要确定使用的迭代器，甚至可能需要确定使用的比较器。这可以通过公共函数签名（我会这样做）或具有纯虚接口的基类来完成（我不建议这样做）。请注意，选择运行时比较器的开销是非常大的。由于固定的迭代器选择或指向函数的指针或虚方法调用的开销，在算法的递归调用中没有被执行时，对于任何合理大小的容器来说都很便宜。

- Yakk - Adam Nevraumont