这是一段执行插入排序的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.我尝试的第一种方法是使用三元运算符：
(重复)？(elements [j]> tempElement):( elements [j]< tempElement) 它看起来有点奇怪,我知道它不是解决问题的最佳方法,所以我尝试了这个： elements [j](reverse)？(<):(>)tempElement
但它不正确,不起作用.此外,三元运算符使if语句中的基本运算数增加了一倍.我知道它只是一个插入排序,它执行Θ(n ^ 2)操作(不是排序很多元素的最佳方式),但我认为有更好的方法来编写它.另一件事是你不能使用这个：
(重复)？( – 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;
}
}