我希望有人能帮助我完成这项任务。所以我们从我的教授那里得到了这个 C++ 算法:
template<class T> //Parameterized by the Type T
void insertion_sort(array<T>& A) //A is an array of Ts
//Permutes the elements of A into ascending sorted order
//The lower index bound of A is assumed to be 1
{ int n = A.size();
for(int k=2; k<=n; k++)
{ T x = A[k]; //x is a a variable of type T
//Insert x in the sorted sequence A[1], ..., A[k-1]
int i = k-1;
while (i>=1&&x<A[i]) //A[i] is evaluated only if i>=1
{ A[i+1]=A[i];
i--;
}
A[i+1]=x;
}
}
好的。现在我必须在第 5 行和第 6 行之间使用函数 A.resize(0, n) 以便 while 函数中的语句“i>=1”变得不必要。我知道当使用这个函数时,A 的索引下限变为 0 而不是 1。但是我看不到它有任何用处,因为我仍然需要在 while 中使用该语句。有人有想法吗?
我将不胜感激。
提前致谢!
最佳答案
要排除i>=1
条件,可以将最小的数组元素移动到主循环之前的第一个位置。
现在这个元素变成了“哨兵”,它的存在排除了超出数组范围。
如果确实需要使用您的resize
,那么只需将最小的可能值(查看 lowest )设置为索引为 0 的新元素。
我们无法从某些库中了解“魔法”例程
关于c++ - 如何在插入排序中使用 replace() 使语句变得不必要,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58466283/