c++ - 如何在插入排序中使用 replace() 使语句变得不必要

Question

我希望有人能帮助我完成这项任务。所以我们从我的教授那里得到了这个 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 中使用该语句。有人有想法吗？

我将不胜感激。

提前致谢!

Answer 1

要排除i>=1条件，可以将最小的数组元素移动到主循环之前的第一个位置。
现在这个元素变成了“哨兵”，它的存在排除了超出数组范围。

如果确实需要使用您的resize，那么只需将最小的可能值(查看 lowest )设置为索引为 0 的新元素。

我们无法从某些库中了解“魔法”例程