作者：未知 来源：月光软件站 加入时间：2005-2-28　月光软件站

搜集了几个常用的排序算法：如直接插入排序，折半插入排序，希尔排序，起泡排序，快速排序，选择排序，堆排序，主要参照《数据结构（C语言版）》

#define MAXSIZE 100
template<class T>
class CSortArithmethic
{
public:

 static struct _tagSqList
 {
  T r[MAXSIZE];
  int length;
 };
private:
 typedef _tagSqList SqList;
public:
 // 直接插入排序
 static void InsertSort(SqList& l);
 // 折半插入排序
 static void BInsertSort(SqList& l);
 //希尔排序
 static void ShellSort(SqList& l,int dlta[],int n);
 // 起泡排序
 static void BubbleSort(SqList& l);
 // 快速排序
 static void QuickSort(SqList& l);
  // 选择排序
 static void SelectSort(SqList& l);
 // 堆排序
 static void HeadSort(SqList& l); //采用顺序表存储表示
 
 static void swapT(T& t1,T& t2);
private:
 static void shellInsert(SqList& l,int dk);
 static void qSort(SqList& l,int low,int high);
};

template<class T>
void CSortArithmethic<T>::InsertSort(SqList& l)
{
 T tTemp;
 int j=0;
 for(int i=1;i<l.length;i++)
 {
  if(l.r[i] <l.r[i-1])
  {
   tTemp = l.r[i];
   for(j= i-1;j>=0&&tTemp <= l.r[j]; --j)
   {
    l.r[j+1] = l.r[j];
   }
   l.r[j+1] = tTemp;
  }
 }
}
template<class T>
void CSortArithmethic<T>::BInsertSort(SqList& l)
{
 T tTemp;
 int low,high;
 int mid;
 int j=0;
 for(int i=1;i<=l.length;i++)
 {
  tTemp = l.r[i];
  low = 0;high = i - 1;
  while(low<high)
  {
   mid = (low + high) / 2;
   if(tTemp <= l.r[mid]) high = mid -1;
   else low = mid +1;
  }
  for( j = i-1;j>=high+1; --j)
   l.r[j+1] = l.r[j];
  l.r[high+1] = tTemp;
 }
}
template<class T>
void CSortArithmethic<T>::shellInsert(SqList& l,int dk)
{
 int i=0;
 int j=0;
 T temp;
 for(i = dk;i<l.length;++i)
 {
  if(l.r[i] < l.r[i - dk])
  {
   temp = l.r[i];
   for(j = i-dk; j>0&&(temp<l.r[j]);j-=dk)
   {
    l.r[j+dk] = l.r[j];
   }
   l.r[j+ dk] = temp;
  }
 }
}
template<class T>
void CSortArithmethic<T>::ShellSort(SqList& l,int dlta[],int n)
{
 for(int i=0;i<n;i++)
  shellInsert(l,dlta[i]);
}
template<class T>
void CSortArithmethic<T>::BubbleSort(SqList& l)
{
 for(int i= l.length;i>=0;i--)
 {
  for(int j=0;j<i-1;j++)
  {
   if(l.r[j+1] < l.r[j])
    swapT(l.r[j],l.r[j+1]);
  }
 }
}
template<class T>
void CSortArithmethic<T>::swapT(T& t1,T& t2)
{
 T temp = t2;
 t2 =t1;
 t1 =temp;
}

template<class T>
void CSortArithmethic<T>::qSort(SqList& l,int low,int high)
{
    int i,j;
    int middle;
    i = low;
    j = high;
 T temp = l.r[(low+high)/2];

    do{
        while((l.r[i]<temp) && (i<high))
            i++;          
        while((l.r[j]>temp) && (j>low))
            j--;
        if(i<=j)
        {
            swapT(l.r[i],l.r[j]);
   i++;
   j--;
        }
    }while(i<=j);

    if(low<j)
        qSort(l,low,j);
    if(high>i)
        qSort(l,i,high);

}
template<class T>
void CSortArithmethic<T>::QuickSort(SqList& l)
{
 qSort(l,0,l.length-1);
}

template<class T>
void CSortArithmethic<T>::SelectSort(SqList& l)
{
 int smallIndex;
 int i,j;
 for(i=0;i<l.length;i++)
 {
  smallIndex = i;
  for(j=i+1;j<l.length;j++)
  {
   if(l.r[smallIndex] > l.r[j])
    smallIndex =j;
  }
  swapT(l.r[i],l.r[smallIndex]);
 }
}
template<class T>
void CSortArithmethic<T>::HeadSort(SqList& l)
{
 for(int i=(l.length-1) /2 ; i>=0; i--)
 {
  T rc = l.r[i];
  for(int j=2 * i;j<= l.length-1; j *= 2)
  {
   if(j< l.length && (l.r[j] < l.r[j+1])) j++;
   if( rc >= l.r[j]) break;
   l.r[i] = l.r[j];
   i = j;
  }
  l.r[i] = rc;
 }
 for( i = l.length-1; i>0;i--)
 {
  swapT(l.r[0],l.r[i]);
  T r = l.r[i];
  for(int j=2 * i;j<= l.length-1; j *= 2)
  {
   if(j< l.length && (l.r[j] < l.r[j+1])) j++;
   if( r >= l.r[j]) break;
   l.r[i] = l.r[j];
   i = j;
  }
  l.r[i] = r;
 }
}
/*
************************************************
综合比较各种内部排序方法,大致结果如下
排序方法 平均时间 最坏情况 辅助存储
简单排序 O(n*n)  O(n*n)  O(1)
快速排序 O(nlogn) O(n*n)  O(logn)
堆排序  O(nlogn) O(nlogn) O(1)

************************************************
*/

/*
*************************************************************************************************
            TEST
*************************************************************************************************
*/
int _tmain(int argc, _TCHAR* argv[])
{
 cout<<"\nSortArithmetic--------------------------------"<<endl;

 CSortArithmethic<int>::_tagSqList list;

 for(int i=0;i<MAXSIZE;i++)
 {
  list.r[i] = i *rand()% MAXSIZE;
 }
 list.length = 100;
 cout<<" befor sort"<<endl;
 for(i=0;i<list.length;i++)
  cout<<list.r[i]<<endl;

 cout<<" after sort"<<endl;
 CSortArithmethic<int>::QuickSort(list);

 for(i=0;i<list.length;i++)
  cout<<list.r[i]<<endl;
}

相关软件：