//9_11.h
#ifndef ARRAY_BASED_SORTING_FUNCTIONS
#define ARRAY_BASED_SORTING_FUNCTIONS

//用直接插入排序法對數組A中的元素進行升序排列
template <class T>
void InsertionSort(T A[], int n)
{
   int i, j;
   T   temp;

   // 將下標為1～n-1的元素逐個插入到已排序序列中適當的位置
   for (i = 1; i < n; i++) 
   {
      //從A[i-1]開始向A[0]方向掃描各元素,尋找適當位置插入A[i]
      j = i;
      temp = A[i];
      while (j > 0 && temp < A[j-1]) 
      { //逐個比較，直到temp>=A[j-1]時，j便是應插入的位置。
        //若達到j==0，則0是應插入的位置。
         
         A[j] = A[j-1];    //將元素逐個后移，以便找到插入位置時可立即插入。
         j--;
      }
      // 插入位置已找到，立即插入。
      A[j] = temp;
   }
}
#endif