搜集了几个常用的排序算法：如直接插入排序，折半插入排序，希尔排序，起泡排序，快速排序，选择排序，堆排序，主要参照《数据结构（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;
}
