//優化的插入排序類
#if !defined(AFX_ImprovedInsertSorter)
#define AFX_ImprovedInsertSorter



#include "InsertSorter.h"
template <class Record,class Compare>
class ImprovedInsertSorter:public InsertSorter<Record,Compare>
{
public:
	void Sort(Record Array[],int n);
};

//優化的插入排序，Array[]為待排序數組，n為數組長度
template <class Record,class int_intCompare>
void ImprovedInsertSorter<Record,int_intCompare>::Sort(Record Array[], int n) 
{ 
	Record TempRecord;
	// 依次插入第i個記錄
	for (int i=1; i<n; i++) 
	{
		TempRecord=Array[i];
		int j = i-1;
		//從i開始往前尋找記錄i的正確位置
		while ((j>=0) && (int_intCompare::lt(TempRecord, Array[j])))
		{    
			Array[j+1] = Array[j];	//將那些大于等于記錄i的記錄后移
			j = j - 1;
		}
		//此時j后面就是記錄i的正確位置，回填
		Array[j+1] = TempRecord; 
	}
}

#endif