//優(yōu)化的起泡排序類

#include "Sorter.h"

template <class Record,class Compare>
class ImprovedBubleSorter:public Sorter<Record,Compare>
{
public:
	void Sort(Record Array[],int n);
};

//優(yōu)化的起泡排序，Array[]為待排序數(shù)組，n為數(shù)組長度
template <class Record,class Compare>
void ImprovedBubleSorter<Record,Compare>::Sort(Record Array[], int n) 
{ 
  bool NoSwap;			// 是否發(fā)生了交換的標(biāo)志
  for (int i=1; i<n; i++)    {
    NoSwap = true;			// 標(biāo)志初始為假
    for (int j=n-1; j>=i; j--)
      if (Compare::lt(Array[j], Array[j-1])) {
        swap(Array, j, j-1);	//如果發(fā)生了交換，標(biāo)志為真
        NoSwap = false;
      }
    if (NoSwap)  // 如果沒發(fā)生過交換，表示已排好序，結(jié)束算法
      return;
    } 
}