排序算法 - 方法

Question

我必须使用面向对象的方法来实现三种不同的排序算法，并且我一直在考虑与之对抗的最佳方法。

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

- >分类（类，接口，多态）

继承：

- >冒泡排序

- >插入排序

- > QuickSort

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

我的问题是：

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

• 有没有范围让我使用模板？即如果我想使用Bubble，它会调用冒泡排序，如果我想使用Insertion，它会调用Insertion？

Answer 1

随着尽量使用接口（纯虚类）

接口方法：当你要排序

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 2

Sort应该是一个接口或抽象类，而bubble/insertion/quick-sort应该是实现/具体类。

这也是值得了解以下内容：

策略模式：

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

和

状态模式：

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

至于模板，我不认为这是值得的，你的情况。

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

性病::排序（通常？）一个快速排序。但该界面适用于快速，泡泡和插入排序。

这种方法的一大优点是一种可以使用另一种。例如，尽管大数据集上的快速排序速度较快，但通常在小数据集上，插入排序的简单性会得到提高（较低的常数因子，即使存在n^2开销）。因此，通过编写这样的排序，当元素数量很少时，快速排序的递归调用可以变为插入排序。

现在，如果您需要运行时替换您正在使用的算法，则需要确定您正在使用的迭代器，甚至可能是比较器。这可以通过一个通用的函数签名（我会这样做）或者一个纯虚拟接口的基类来实现（我建议不要这样做）。请注意，运行时选择的比较器的开销并不重要，但是。对于任何合理大小的容器来说，只要不是在算法的递归调用中完成，来自固定迭代器选项或指向函数或虚方法调用的开销将非常便宜。