如何使用插入排序中的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。但是我看不到有任何用处，因为我仍然需要那条语句。有人有主意吗？

我将非常感谢。

谢谢您！

Answer 1

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

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