//直接插入排序類
#include "InsertSorter.h"
template <class Record,class Compare>
class StraightInsertSorter:public InsertSorter<Record,Compare>
{
public:
	void Sort(Record Array[],int n);
};

//直接插入排序，Array[]為待排序數組，n為數組長度
template <class Record,class Compare>
void StraightInsertSorter<Record,Compare>::Sort(Record Array[], int n) 
{ 
	// 依次插入第i個記錄
	for (int i=1; i<n; i++) 
	{
		//依次與前面的記錄進行比較，如果發現比它小的記錄，就交換
		for (int j=i;j>0;j--)
		{
			if (Compare::lt(Array[j], Array[j-1]))
				swap(Array, j, j-1);
			else break;		//此時i前面的所有記錄(包括i)已排好序		
		}
	}
}