C++ Exercises（十五）--排序算法的简单实现

structNode
{//队列结点
intdata;
structNode*pNext;
};
classCQueue
{//队列类(带头结点）
public:
CQueue(void);
~CQueue(void);
boolisEmpty()const;//是否为空
voidEnQueue(intnum);//入队列
intDeQueue();//出队列
intFront()const;//对头元素
voidclearQueue();//清空队列
intSize()const;
voidprintQueue()const;
private:
Node*front;//头结点
Node*end;//尾结点
intsize;//队列大小

};
#include"Queue.h"
#include<cstdlib>
#include<assert.h>
#include<iostream>
usingnamespacestd;

CQueue::CQueue(void)
{
this->front=newNode;
this->front->pNext=NULL;
this->end=this->front;
this->size=0;
}
voidCQueue::EnQueue(intnum)
{//入队列
Node*pNum=newNode;
pNum->data=num;
pNum->pNext=NULL;
this->end->pNext=pNum;
this->end=pNum;
this->size++;
}
intCQueue::DeQueue()
{//出队列，返回对头元素值
assert(this->front!=this->end);//队列不空
intresult;
Node*pNum=this->front->pNext;
result=pNum->data;
if(pNum==this->end)
{//队列中只有一个元素了
this->front->pNext=NULL;
this->end=this->front;
}
else
{
this->front->pNext=pNum->pNext;
}
deletepNum;
this->size--;
returnresult;
}
voidCQueue::clearQueue()
{//清空队列
if(!this->isEmpty())
{
Node*pNum=this->front->pNext;//指向第一个结点
Node*pre=this->front;
while(pNum!=NULL)
{
pre=pNum;
deletepre;
pNum=pNum->pNext;
}
this->front->pNext=NULL;
this->end=this->front;
this->size=0;
}

}
voidCQueue::printQueue()const
{
if(!this->isEmpty())
{
Node*pNum=this->front->pNext;
while(pNum!=NULL)
{
cout<<pNum->data<<"";
pNum=pNum->pNext;
}
cout<<endl;
}
}
intCQueue::Size()const
{
returnthis->size;
}
boolCQueue::isEmpty()const
{
returnthis->front==this->end;
}
CQueue::~CQueue(void)
{
this->clearQueue();
}

<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->#include"Queue.h"
#include<iostream>
usingnamespacestd;

voidprintArray(intdata[],intn)
{
inti;
for(i=0;i<n;++i)
{
cout<<data[i]<<"";
}
cout<<endl;
}
intgetRadix(intnum,intcount)
{//返回num在趟数为count时的数值,0趟最后一位，趟倒数第一位，依次类推
inttemp=num,result,nCount=0;
while(nCount<=count)
{
result=temp%10;
temp=temp/10;
nCount++;
}
returnresult;
}
voidRadixSort(intdata[],intn,constintcount)
{//基数排序,count为趟数
CQueue*queue=newCQueue[10];//下标从到的个队列
inti,j,num,m;
//
for(i=0;i<count;++i)
{
//分配
for(j=0;j<n;++j)
{
num=getRadix(data[j],i);//当前趟数下的基数
queue[num].EnQueue(data[j]);
}
for(j=0;j<10;++j)
{
cout<<"队列"<<j<<":"<<endl;
queue[j].printQueue();
}

//收集
m=0;
for(j=0;j<10;++j)
{
while(!queue[j].isEmpty())
{
data[m]=queue[j].DeQueue();
m++;
}

}
cout<<"收集趟数:"<<i<<":"<<endl;
printArray(data,n);
}
}

voidswap(int&a,int&b)
{
inttemp=a;
a=b;
b=temp;
}
intminElement(intdata[],intbegin,intend)
{
intresult=begin,maxNum=data[begin],i;
for(i=begin+1;i<end;++i)
{
if(data[i]<maxNum)
{
maxNum=data[i];
result=i;
}
}
returnresult;
}
voidSelectionSort(intdata[],intn)
{//选择排序
inti,num;
//共需要进行n-1轮
for(i=0;i<n-1;++i)
{
num=minElement(data,i,n);
swap(data[i],data[num]);
}
}
voidAdjustHeap(intdata[],intbegin,intend)
{//堆调整data[beginend-1]
inttmp=data[begin];
intc=begin*2,pos=begin;
while(c<=end)
{
if(c<end&&data[c+1]>data[c])
{
c++;
}
if(data[c]>tmp)
{
data[pos]=data[c];
pos=c;
c=c*2;

}
else
break;
}
data[pos]=tmp;
}
voidBuildHeap(intdata[],intn)
{//初始建小顶堆
inti;
for(i=n/2;i>0;--i)
{
AdjustHeap(data,i,n);
}

}

voidHeapSort(intdata[],intn)
{//堆排序
int*tdata=newint[n+1];
inti;
tdata[0]=-1;//第一个元素舍弃
for(i=0;i<n;++i)
{
tdata[i+1]=data[i];
}
BuildHeap(tdata,n);//将tdata[1n]建成初始堆
for(i=n-1;i>=1;--i)
{//对当前无序区进行堆排序，共做n-1趟。
swap(tdata[1],tdata[i+1]);
AdjustHeap(tdata,1,i);//重新调整为堆
}
for(i=0;i<n;++i)
{
data[i]=tdata[i+1];
}
delete[]tdata;
}

voidBubbleSort(intdata[],intn)
{//冒泡排序
boolisChange=true;
inti,k;
for(k=n-1;k>=1&&isChange==true;--k)
{
isChange=false;
for(i=0;i<k;++i)
{
if(data[i]>data[i+1])
{
swap(data[i],data[i+1]);
isChange=true;
}
}
}
}

voidInsertSort(intdata[],intn)
{//插入排序
inti,j,pos,num;
for(i=1;i<n;++i)
{
num=data[i];
for(j=0;j<=i-1&&data[i]>data[j];++j);
pos=j;//插入点
for(j=i-1;j>=pos;--j)
{
data[j+1]=data[j];
}
data[pos]=num;
}
}
voidQuickSort(int*data,intlow,inthigh)
{//快速排序
intpivot;
intscanUp,scanDown;
intmid;
if(high-low<=0)
return;
else
{
if(high-low==1)
{
if(data[high]<data[low])
swap(data[low],data[high]);
return;
}
mid=(low+high)/2;
pivot=data[mid];
swap(data[low],data[mid]);
scanUp=low+1;
scanDown=high;
do
{
while(scanUp<=scanDown&&data[scanUp]<=pivot)
scanUp++;
while(data[scanDown]>pivot)
scanDown--;
if(scanUp<scanDown)
swap(data[scanUp],data[scanDown]);
}while(scanUp<scanDown);
data[low]=data[scanDown];
data[scanDown]=pivot;
if(low<scanDown-1)
QuickSort(data,low,scanDown-1);
if(scanDown+1<high)
QuickSort(data,scanDown+1,high);
}
}
intmain()
{
inta[]={10,32,55,41,39,12,11,15,20,19,21,22,29,25};
intlen=sizeof(a)/sizeof(int);
cout<<"排序前:"<<endl;
printArray(a,len);
//RadixSort(a,len,2);
//SelectionSort(a,len);
//HeapSort(a,len);
//BubbleSort(a,len);
//InsertSort(a,len);
QuickSort(a,0,len);
cout<<"排序后:"<<endl;
printArray(a,len);
system("pause");
return0;
}