c++ - 我需要帮助来理解编程挑战

Question

我正在尝试做一些家庭作业，但无法全神贯注于一个问题。我已经在类(class)讨论区发帖并给教授发了电子邮件，但没有得到任何帮助。

问题是:设计一个 abstractSort 类，可用于分析排序算法执行的比较次数。该类应该有一个能够比较两个数组元素的成员函数 compare，以及一种跟踪执行的比较次数的方法。该类应该是一个带有纯虚成员函数的抽象类

virtual void Sort(int arr[], int size)= 0;

当被覆盖时，将通过调用比较函数确定数字对的相对顺序(这是我不明白的短语)对数组进行排序。创建AbstractSort的子类，使用简单的排序算法实现排序功能。该类应该有一个成员函数，可以在排序完成后调用该成员函数以确定执行的比较次数。

我知道如何对此进行编码，但我只是不认为我会按照问题的措辞方式进行处理。我已经编写了代码来通过递增计数器并输出该数字来跟踪比较。然而，这个问题困扰着我。作者说“通过调用比较函数确定数字对的相对顺序”是什么意思

有人知道他们的意思吗？我只是把一个明显的问题复杂化了，还是有一些我看不到的微妙挑战。正如我所说，我不需要帮助编码问题，只需要理解问题。

Answer 1

在大多数排序算法的普通实现过程中的某个时候，您会遇到这样的事情:

if (elements[i] < elements[j]) {
    // Do something
}
else {
    // Do something else
}

将比较元素的工作“外包”到一个单独的函数通常很方便(为简单起见，我假设要排序的元素是整数):

protected:
bool isSmaller(int a, int b) {
    return a < b;
}

// Inside sorting function:
if (isSmaller(elements[i], elements[j])) { ... } else { ... }

结合继承，你可以定义isSmaller()在基类中，对于您想要实现的每个排序算法(快速排序、归并排序、插入排序...)，您需要创建一个新的子类。但是，每个子类都应调用 isSmaller()而不是使用 <以确定哪些元素应该放在哪个元素之前。然后，您可以将您的“计算比较次数”代码(如您所说，这将包括简单地增加一个计数器)到 isSmaller() .

(任务的重点是让你意识到继承可以让你不必在每个排序算法实现中重复计数代码。另外，当使用函数指针或函数对象时，“外包”比较的想法也可以用来制作一个“可配置”的排序类，类的用户可以决定如何进行比较，例如，按降序对数字进行排序，或根据姓名对人员列表进行排序等)