c++ - 排序算法 - 方法

Question

我必须使用面向对象的方法来实现三种不同的排序算法，并且我一直在考虑解决这个问题的最佳方法。

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

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

继承：

-> 冒泡排序

-> 插入排序

-> 快速排序

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

我的问题是：

• 这是一个很好的使用方法吗？

• 我有使用模板的空间吗？即如果我想使用Bubble，它会调用冒泡排序，如果我想使用Insertion，它会调用Insertion？

Answer 1

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

以下内容也值得学习：

策略模式：

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

和

状态模式：

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

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

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);

Answer 3

The right way to do this in C++ is via templates.

Sorting something is an algorithm, and it generally has little to no persistent state. A sort isn't an object -- it is a function on data (which may be objects).

The std library already has a sort, with this signature:

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

The iterators begin and end denote a range of values to be sorted, and comp is a functor (or function) that when passed two elements of the range of values tells you if the first one is less than the second.

To use this on a std::vector, you'd do something like this:

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

The std::sort is (usually?) a quicksort. But the interface works for quick, bubble and insertion sort.

The big advantage of this approach is that one sort can use another. As an example, while a quicksort is faster on large data sets, often on small data sets the simplicity of insertion sort wins (lower constant factor, even with the n^2 overhead). So by writing your sorts like this, quicksort's recursive calls can instead become insertion sort when the number of elements is small.

Now, if you need run-time substitution of which algorithm you are using, you'll need to pin down what iterators you are using, and maybe even what comparitor. This can be done with either a common function signature (what I'd do), or a base class with a pure virtual interface (which I would advise against). Note that the overhead for a run-time chosen comparitor is non-trivial, however. The overhead from a fixed iterator choice, or from a pointer-to-function or virtual method call, so long as it isn't done in the recursive calls of your algorithm, will be pretty cheap for any reasonable sized container.