这是一段执行插入排序的 C++ 代码:
#ifndef INSERTIONSORT
#define INSERTIONSORT
template<class T>
void insertionSort(T* elements, int size, int reverse = 0) {
T tempElement;
int j;
for (int i = 0; i < size; ++i) {
tempElement = elements[i];
for (j = i - 1; j >= 0 && elements[j] > tempElement; j--)
elements[j + 1] = elements[j];
elements[j + 1] = tempElement;
}
}
#endif
不重复代码我写不出来。这不是我第一次遇到这种问题。我只需要替换 <
至 >
, 当 reverse
= 1. 我尝试的第一种方法是使用三元运算符:
(repeat)?(elements[j] > tempElement):(elements[j] < tempElement)
它看起来有点奇怪,我知道这不是解决问题的最佳方法,所以我尝试了这个:
elements[j] (reverse)?(<):(>) tempElement
但它不正确并且不起作用。三元运算符还使 if 语句中的基本运算数量增加了一倍。我知道它只是一个执行 Θ(n^2) 操作的插入排序(不是对很多元素进行排序的最佳方式),但我认为有更好的方式来编写它。另一件事是你不能使用这个:
(repeat)?(-1):(1) * (elements[j] - tempElement) > 0
因为类T只能有operator=和operator>(运算符<)。您也不能在循环中调用函数,因为它将是 Θ(n) 或 Θ(n^2) 调用。这是最后一个解决方案:
#ifndef INSERTIONSORT
#define INSERTIONSORT
template<class T>
void insertionSort(T* elements, int size, int reverse = 0) {
T tempElement;
int j;
if (reverse)
for (int i = 0; i < size; ++i) {
tempElement = elements[i];
for (j = i - 1; j >= 0 && elements[j] < tempElement; j--)
elements[j + 1] = elements[j];
elements[j + 1] = tempElement;
}
else
for (int i = 0; i < size; ++i) {
tempElement = elements[i];
for (j = i - 1; j >= 0 && elements[j] > tempElement; j--)
elements[j + 1] = elements[j];
elements[j + 1] = tempElement;
}
}
#endif
唯一的问题是重复代码。编程的主要原则是:“不要重复自己”(D.R.Y)。我真的不知道如何在这里正确编写代码。
最佳答案
您可以添加一个比较器作为类型,如下例所示:
template<template<class> class COMP = std::less, typename T>
void insertionSort(T* elements, int size) {
T tempElement;
int j;
COMP<T> pred;
for (int i = 0; i < size; ++i) {
tempElement = elements[i];
for (j = i - 1; j >= 0 && pred(tempElement, elements[j]); --j)
elements[j + 1] = elements[j];
elements[j + 1] = tempElement;
}
}
关于c++ - 倒序排序。 "Don' t 重复你自己”规则,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24663303/