C++实现各种排序算法类汇总
C++可实现各种排序算法类，比如直接插入排序、折半插入排序、Shell排序、归并排序、简单选择排序、基数排序、对data数组中的元素进行希尔排序、冒泡排序、递归实现、堆排序、用数组实现的基数排序等。
具体代码如下：
#ifndefSORT_H
#defineSORT_H
#include<iostream>
#include<queue>
usingnamespacestd;
//1.直接插入排序
template<classElemType>
voidInsertSort(ElemTypedata[],intn);
//2.折半插入排序
template<classElemType>
voidBInsertSort(ElemTypedata[],intn);
//3.Shell排序
//对data数组中的元素进行希尔排序，n为该数组大小
//increments为增量序列，incrementsLength为增量序列的大小
template<classElemType>
voidShellSort(ElemTypedata[],intincrements[],intn,intincrementsLength);
//1.BubbleSort
template<classElemType>
voidBubbleSort(ElemTypedata[],intn);
//2.快速排序
template<classElemType>
voidQuickSort(ElemTypedata[],intn);
//////////////////
//MergeSort
//////////////////
//归并排序
template<classElemType>
voidMergeSort(ElemTypedata[],intn);
template<classElemType>
voidMergeSortNonRecursion(ElemTypedata[],intn);
//////////////////
//Selectionsort
//////////////////
//简单选择排序
template<classElemType>
voidSelectionSort(ElemTypedata[],intn);
//堆排序
template<classElemType>
voidHeapSort(ElemTypedata[],intn);
///////////////
//RadixSort
///////////////
//静态链表结点
constintDIGITS=10;
constintRADIX=10;
classSLList;
ostream&operator<<(ostream&os,SLList&s);//由于VC++6.0使用usingnamespacestd对于友元不支持
//故在类SLList之前做前向声明
//若使用其他C++编译器，这两句可删去
//静态链表staticlinkedlist
//[0]：头结点
classSLList
{
structNode
{
intkey[DIGITS];
intinfo;
intnext;
};
friendostream&operator<<(ostream&os,SLList&s);
public:
SLList():data(NULL),length(0){};
~SLList();
voidArrange();
voidInit(intarr[],intn);
voidRadixSort();
private:
voidDistribute(int[],int[],int);
voidCollection(int[],int[],int);
Node*data;
intlength;
};
//基数排序
voidRadixSort(intdata[],intn);
//voidRadixSort(SLList&);
///////////////
//util
///////////////
template<classElemType>
voidSwap(ElemType&a,ElemType&b)
{
ElemTypec=a;
a=b;
b=c;
}
intinit(int**data);
template<classElemType>
voidprint(ElemTypedata[],intbegin,intend);
//直接插入排序,数组data用于存放待排序元素，n为待排序元素个数
template<classElemType>
voidInsertSort(ElemTypedata[],intn)
{
ElemTypetmp;
inti,j;
for(i=1;i<n;i++){
if(data[i]>data[i-1])
continue;
tmp=data[i];//保存待插入的元素
data[i]=data[i-1];
for(j=i-1;j>0&&data[j-1]>tmp;j--)
data[j]=data[j-1];//元素后移
data[j]=tmp;//插入到正确位置
}
}
//折半插入排序
template<classElemType>
voidBInsertSort(ElemTypedata[],intn)
{
ElemTypetmp;
inti,j,mid,low,high;
for(i=1;i<n;i++){
tmp=data[i];//保存待插入的元素
low=0;
high=i-1;
while(low<=high){//在data[low..high]中折半查找有序插入的位置
mid=(low+high)/2;//折半
if(tmp<data[mid])
high=--mid;//插入点在低半区
else
low=++mid;//插入点在高半区
}
for(j=i-1;j>=low;j--)
data[j+1]=data[j];//元素后移
data[low]=tmp;//插入到正确位置
}
}
//对data数组中的元素进行希尔排序，n为该数组大小
//increments为增量序列，incrementsLength为增量序列的大小
template<classElemType>
voidShellSort(ElemTypedata[],intincrements[],intn,intincrementsLength)
{
inti,j,k;
ElemTypetmp;
for(k=0;k<incrementsLength;k++){//进行以increments[k]为增量的排序
for(i=increments[k];i<n;i++){
tmp=data[i];
for(j=i;j>=increments[k];j-=increments[k]){
if(tmp>=data[j-increments[k]])
break;
data[j]=data[j-increments[k]];
}
data[j]=tmp;
}
}
}
//冒泡排序
template<classElemType>
voidBubbleSort(ElemTypedata[],intn)
{
intlastSwapIndex=n-1;//用于记录最后一次交换的元素下标
inti,j;
for(i=lastSwapIndex;i>0;i=lastSwapIndex)
{
lastSwapIndex=0;
for(j=0;j<i;j++)
if(data[j]>data[j+1]){
Swap(data[j],data[j+1]);
lastSwapIndex=j;
}
}
}
//快速排序
template<classElemType>
intPartition(ElemTypedata[],intlow,inthigh)
{
ElemTypepivot=data[low];
while(low<high){
while(low<high&&data[high]>=pivot)
high--;
data[low]=data[high];
while(low<high&&pivot>=data[low])
low++;
data[high]=data[low];
}
data[low]=pivot;
returnlow;
}
template<classElemType>
voidQuickSort(ElemTypedata[],intbegin,intend)
{
if(begin>=end)
return;
intpivot=Partition(data,begin,end);
QuickSort(data,begin,pivot-1);
QuickSort(data,pivot+1,end);
}
template<classElemType>
voidQuickSort(ElemTypedata[],intn)
{
if(n<2)
return;
QuickSort(data,0,n-1);
}
//将数组data中，[lptr...rptr-1][rptr...rightEnd]两部分的元素进行合并
//tmpArr为合并时的辅存空间
template<classElemType>
voidMerge(ElemTypedata[],ElemTypetmpArr[],intlptr,intrptr,intrightEnd)
{
intleftEnd=rptr-1;
intptr,i;
ptr=i=lptr;
while(lptr<=leftEnd&&rptr<=rightEnd)
if(data[lptr]<=data[rptr])
tmpArr[ptr++]=data[lptr++];
else
tmpArr[ptr++]=data[rptr++];
while(lptr<=leftEnd)
tmpArr[ptr++]=data[lptr++];
while(rptr<=rightEnd)
tmpArr[ptr++]=data[rptr++];
for(;i<=rightEnd;i++)
data[i]=tmpArr[i];
}
//递归实现
//将数组data中，[begin...end]的元素进行归并排序
template<classElemType>
voidMSort(ElemTypedata[],ElemTypetmpArr[],intbegin,intend)
{
intmiddle;
if(begin>=end)
return;
middle=(begin+end)/2;//将data平分为[begin..middle]和[middle..end]
MSort(data,tmpArr,begin,middle);//递归前半部分
MSort(data,tmpArr,middle+1,end);//递归后半部分
Merge(data,tmpArr,begin,middle+1,end);//将data[begin..middle]，data[middle..end]进行归并
}
template<classElemType>
voidMergeSort(ElemTypedata[],intn)
{
ElemType*pArr=NULL;
pArr=newElemType[n];
MSort(data,pArr,0,n-1);
delete[]pArr;
}
//非递归实现
template<classElemType>
voidMPass(ElemTypedata[],ElemTypetmpArr[],intn,intmergeLength)
{
inti=0;
while(i<=n-2*mergeLength){
Merge(data,tmpArr,i,i+mergeLength,i+2*mergeLength-1);
i=i+2*mergeLength;
}
if(i+mergeLength<n)
Merge(data,tmpArr,i,i+mergeLength,n-1);
}
template<classElemType>
voidMergeSortNonRecursion(ElemTypedata[],intn)
{
intmergeLength=1;
ElemType*pArr=NULL;
pArr=newElemType[n];
while(mergeLength<n){
MPass(data,pArr,n,mergeLength);
mergeLength*=2;
}
delete[]pArr;
}
//简单选择排序
template<classElemType>
voidSelectionSort(ElemTypedata[],intn)
{
inti,j,min;
for(i=0;i<n;i++){
min=i;
for(j=i+1;j<n;j++){
if(data[j]<data[min])
min=j;
}
Swap(data[i],data[min]);
}
}
//堆排序
//i为指定元素在数组中的下标
//返回指定结点的左孩子在数组中的下标
inlineintLeftChild(inti)
{
return2*i+1;
}
template<classElemType>
voidHeapAdjust(ElemTypedata[],inti,intn)
{
ElemTypetmp;
intchild;
for(tmp=data[i];LeftChild(i)<n;i=child){
child=LeftChild(i);
if(child!=n-1&&data[child+1]>data[child])//取较大的孩子结点
child++;
if(tmp<data[child])
data[i]=data[child];
else
break;
}
data[i]=tmp;
}
template<classElemType>
voidHeapSort(ElemTypedata[],intn)
{
inti;
for(i=n/2;i>=0;i--)//建堆
HeapAdjust(data,i,n);
for(i=n-1;i>0;i--){//将堆的根结点与最后的一个叶结点交换,并进行调整
Swap(data[0],data[i]);
HeapAdjust(data,0,i);
}
}
//用数组实现的基数排序
voidRadixSort(intdata[],intn)
{
constintradix=10;
constintdigits=10;
inti,j,k,factor;
queue<int>queues[radix];
for(i=0,factor=1;i<digits;i++,factor*=radix){
for(j=0;j<n;j++)
queues[(data[j]/factor)%radix].push(data[j]);//分配
for(k=j=0;j<radix;j++,k++)//收集
while(!queues[j].empty()){
data[k]=queues[j].front();
queues[j].pop();
}
}
}
//分配
voidSLList::Distribute(intfront[],intrear[],intdigit)
{
inti,index;
for(i=0;i<RADIX;i++)
front[i]=0;
for(i=data[0].next;i>0;i=data[i].next){
index=data[i].key[digit];
if(front[index]==0)
front[index]=i;
else
data[rear[index]].next=i;
rear[index]=i;
}
}
//收集
voidSLList::Collection(intfront[],intrear[],intdigit)
{
inti,current;
for(i=0;front[i]==0;i++);//找到第一个非空子表
data[0].next=front[i];//头结点指向第一个非空子表中第一个结点
current=rear[i++];
for(;i<RADIX;i++){
if(front[i]==0)
continue;
data[current].next=front[i];//链接两个非空子表
current=rear[i];
}
data[current].next=0;
}
//用SLList实现的基数排序
voidSLList::RadixSort()
{
inti;
intfront[RADIX],rear[RADIX];
//从最低位优先依次对各关键字进行分配收集
for(i=0;i<DIGITS;i++){
Distribute(front,rear,i);
Collection(front,rear,i);
}
}
SLList::~SLList()
{
delete[]data;
length=0;
}
voidSLList::Init(intarr[],intn)
{
length=n+1;
if(data!=NULL)
delete[]data;
data=newNode[n+1];
data[0].next=1;
for(inti=1;i<=n;i++){
intvalue=data[i].info=arr[i-1];
for(intj=0;j<10;j++){
data[i].key[j]=value%10;//+'0';
value/=10;
}
data[i].next=i+1;
}
data[n].next=0;
}
//根据链表中各结点的指针值调整元素位置，使得SLList中元素按关键字正序排列
voidSLList::Arrange()
{
inti,tmp;
intcurrent=data[0].next;//current存放第一个元素的当前位置
for(i=1;i<length;i++){
while(current<i)//找到第i个元素，并用current存放其在静态链表中当前位置
current=data[current].next;
tmp=data[current].next;
if(current!=i){
Swap(data[current],data[i]);//第i个元素调整到位
data[i].next=current;//指向被移走的元素
}
current=tmp;//为找第i+1个元素做准备
}
}
ostream&operator<<(ostream&os,SLList&s)
{
for(inti=1;i<s.length;i++)
cout<<s.data[i].info<<"";
os<<endl;
returnos;
}
#endif