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

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

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