c++常见排序算法.docx
《c++常见排序算法.docx》由会员分享，可在线阅读，更多相关《c++常见排序算法.docx（18页珍藏版）》请在冰点文库上搜索。
c++常见排序算法
/**<气泡排序，快速排序，插入排序，希尔排序，
选择排序，堆排序，归并排序，基数排序*/
#include
#include
#defineMax100000000
usingnamespacestd;
template
classSortR
{
public:
SortR（）
{
arr=newT[Max];
}
~SortR（）{
delete[]arr;
}
voidInputValue（）;
voidBubbleSort（）;//冒泡排序
voidQuickSort（）;//快速排序
voidInsertSort（）;//插入排序
voidHillSort（）;//希尔排序
voidSelectSort（）;//选择排序
voidHeapSort（）;//堆排序
voidMergeSort（）;//归并排序
voidBaseSort（）;//基数排序
voidDisplay（T*）;//输出排序结果
private:
voidSwap（T*,T*）const;
intfindPivot（int,int,T*）const;
intPartition（int,int,T,T*）const;
voidQuickSortRev（int,int,T*）;//快排递归
voidPushDown（int,int,T*）const;//堆排序，整理堆
voidMerge_array（T*,int,int,int,T*）;//合并两个数组
voidmerge_sort（T*,int,int,T*）;//归并排序，递归实现
TGetDigit（Tx,intd）;
voidmsdradix_sort（T*,int,int,int）;
T*arr;
intn;
};
template
voidSortR:
:
InputValue（）
{
cout<<"输入数组大小：
";
//cin>>n;
n=10000;
cout<<"输入数组元素：
";
srand（（T）time（NULL））;
for（inti=0;i//cin>>arr[i];
arr[i]=rand（）%100000;
}
template
voidSortR:
:
Swap（T*t1,T*t2）const//交换
{
Ttemp;
temp=*t1;
*t1=*t2;
*t2=temp;
}
/**<--------冒泡排序-------*/
template
voidSortR:
:
BubbleSort（）
{
//---时间测试
clock_tstart,finish;
doubletotaltime;
start=clock（）;
//----------------------------------------------------
T*bubble_arr=newT[n];
for（inti=0;ibubble_arr[i]=arr[i];
for（inti=0;i{
for（intj=n-1;j>i;j--）
{
if（bubble_arr[j]Swap（&bubble_arr[j],&bubble_arr[j-1]）;
}
}
finish=clock（）;
totaltime=（double）（finish-start）/CLOCKS_PER_SEC;
cout<<"运行时间：
"<//Display（bubble_arr）;
//Display（arr）;
}
/**<-------快速排序--------*/
template
intSortR:
:
findPivot（inti,intj,T*quick_arr）const
{
Tfirstkey;
intk;
firstkey=quick_arr[i];
for（k=i+1;k<=j;k++）
{
if（quick_arr[k]>firstkey）returnk;
elseif（quick_arr[k]elsereturn-1;//没有不同关键字
}
return0;
}
template
intSortR:
:
Partition（inti,intj,Tpiovt,T*quick_arr）const
{
intl=i,r=j;
do{
Swap（&quick_arr[l],&quick_arr[r]）;
while（quick_arr[l]while（quick_arr[r]>=piovt）r--;
}while（l<=r）;
returnl;
}
template
voidSortR:
:
QuickSortRev（inti,intj,T*quick_arr）
{
Tpiovt;
intpiovtindex;
intk;
piovtindex=findPivot（i,j,quick_arr）;
if（piovtindex>=0）
{
piovt=quick_arr[piovtindex];
k=Partition（i,j,piovt,quick_arr）;
//Display（quick_arr）;//输出
return;
QuickSortRev（i,k-1,quick_arr）;
QuickSortRev（k,j,quick_arr）;
}
}
template
voidSortR:
:
QuickSort（）
{
//---时间测试
clock_tstart,finish;
doubletotaltime;
start=clock（）;
T*quick_arr=newT[n];
for（inti=0;iquick_arr[i]=arr[i];
QuickSortRev（0,n-1,quick_arr）;
//-----------
finish=clock（）;
totaltime=（double）（finish-start）/CLOCKS_PER_SEC;
cout<<"运行时间：
"<//Display（arr）;
}
/*------插入排序------*/
template
voidSortR:
:
InsertSort（）//插入排序
{
//---时间测试
clock_tstart,finish;
doubletotaltime;
start=clock（）;
T*insert_arr=newT[n];
for（inti=0;iinsert_arr[i+1]=arr[i];
insert_arr[0]=-1;
for（inti=1;i{
intj=i;
while（insert_arr[j]{
Swap（&insert_arr[j],&insert_arr[j-1]）;
j--;
}
}
//-----------
finish=clock（）;
totaltime=（double）（finish-start）/CLOCKS_PER_SEC;
cout<<"运行时间：
"<//for（inti=1;i<=20;i++）
//cout<//cout<//Display（arr）;
}
/*-------希尔排序-----------*/
template
voidSortR:
:
HillSort（）
{
//---时间测试
clock_tstart,finish;
doubletotaltime;
start=clock（）;
T*hill_arr=newT[n];
for（inti=0;ihill_arr[i]=arr[i];
intj,gap;
for（gap=n/2;gap>0;gap/=2）
for（j=gap;j{
if（hill_arr[j]{
Ttemp=hill_arr[j];
intk=j-gap;
while（k>=0&&hill_arr[k]>temp）
{
hill_arr[k+gap]=hill_arr[k];
k-=gap;
}
hill_arr[k+gap]=temp;
}
}
//Display（hill_arr）;
//-----------
finish=clock（）;
totaltime=（double）（finish-start）/CLOCKS_PER_SEC;
cout<<"运行时间：
"<}
/*--------选择排序--------*/
template
voidSortR:
:
SelectSort（）
{
//---时间测试
clock_tstart,finish;
doubletotaltime;
start=clock（）;
T*select_arr=newT[n];
for（inti=0;iselect_arr[i]=arr[i];
Tminindex;//存储最小的元素
for（inti=0;i{
minindex=select_arr[i];
for（intj=i+1;j{
if（select_arr[j]{
minindex=select_arr[j];
}
}
Swap（&select_arr[i],&minindex）;
}
//Display（select_arr）;
//-----------
finish=clock（）;
totaltime=（double）（finish-start）/CLOCKS_PER_SEC;
cout<<"运行时间：
"<}
/*--------堆排序---------*/
template
voidSortR:
:
PushDown（intfirst,intlast,T*heap_arr）const
{
intr;
r=first;
while（r<=last/2）
if（（r==last/2）&&（last%2==0））//r有一个儿子，在2*r
{
if（heap_arr[r]>heap_arr[2*r]）
Swap（&heap_arr[2*r],&heap_arr[r]）;
r=last;
}
elseif（（heap_arr[r]>heap_arr[2*r]）&&（heap_arr[2*r]<=heap_arr[2*r+1]））
{//r与左儿子交换
Swap（&heap_arr[2*r],&heap_arr[r]）;
r=2*r;
}
elseif（（heap_arr[r]>heap_arr[2*r+1]）&&（heap_arr[2*r+1]<=heap_arr[2*r]））
{//r与右儿子交换
Swap（&heap_arr[2*r+1],&heap_arr[r]）;
r=r*2+1;
}
elser=last;
}
template
voidSortR:
:
HeapSort（）
{
//---时间测试
clock_tstart,finish;
doubletotaltime;
start=clock（）;
T*heap_arr=newT[n];
for（inti=0;iheap_arr[i+1]=arr[i];
inti;
for（i=n/2;i>=1;i--）
PushDown（i,n,heap_arr）;
for（i=n;i>1;i--）
{
Swap（&heap_arr[1],&heap_arr[i]）;
PushDown（1,i-1,heap_arr）;
}
//-----------
finish=clock（）;
totaltime=（double）（finish-start）/CLOCKS_PER_SEC;
cout<<"运行时间：
"</*for（inti=n;i>0;i--）
cout<cout<}
/*----------归并排序-----------*/
template
voidSortR:
:
Merge_array（T*merge_arr,intfirst,intmidle,intlast,T*temp）
{
inti=first,j=midle+1;
intm=midle,l=last,k=0;
while（i<=m&&j<=l）
{
if（merge_arr[i]<=merge_arr[j]）
temp[k++]=merge_arr[i++];
else
temp[k++]=merge_arr[j++];
}
while（i<=m）
temp[k++]=merge_arr[i++];
while（j<=l）
temp[k++]=merge_arr[j++];
for（i=0;imerge_arr[first+i]=temp[i];
}
template
voidSortR:
:
merge_sort（T*merge_arr,intfirst,intlast,T*temp）
{
if（first{
intmid=（first+last）/2;
merge_sort（merge_arr,first,mid,temp）;
merge_sort（merge_arr,mid+1,last,temp）;
Merge_array（merge_arr,first,mid,last,temp）;
}
}
template
voidSortR:
:
MergeSort（）
{
//---时间测试
clock_tstart,finish;
doubletotaltime;
start=clock（）;
T*merge_arr=newT[n];
for（inti=0;imerge_arr[i+1]=arr[i];
T*p=newT[n];
merge_sort（merge_arr,1,n,p）;
//-----------
finish=clock（）;
totaltime=（double）（finish-start）/CLOCKS_PER_SEC;
cout<<"运行时间：
"</*for（inti=1;i<=n;i++）
cout<cout<}
/*---------基数排序------------*/
template
TSortR:
:
GetDigit（Tx,intd）
{
inta[]={1,1,10};//排的是100以内的
return（x/a[d]）%10;
}
template
voidSortR:
:
msdradix_sort（T*base_arr,intfirst,intlast,intd）
{
intradix=10;
intcount[10],i,j;
for（i=0;icount[i]=0;
T*bucker=newT[n];
for（i=first;i<=last;i++）
count[GetDigit（base_arr[i],d）]++;
for（i=1;icount[i]+=count[i-1];
for（i=last;i>=first;--i）
{
j=GetDigit（base_arr[i],d）;
bucker[count[j]-1]=base_arr[i];
--count[j];
}
for（i=first,j=0;i<=last;i++,j++）
base_arr[i]=bucker[j];
for（i=0;i{
intp1=first+count[i];
intp2=first+count[i+1]-1;
if（p11）
msdradix_sort（base_arr,p1,p2,d-1）;
}
}
template
voidSortR:
:
BaseSort（）
{
/*cout<<"输入所要排的数（先默认0-99的,n值还是最开始的）：
"<T*base_arr=newT[n];
for（inti=0;icin>>base_arr[i];*/
//---时间测试
clock_tstart,finish;
doubletotaltime;
start=clock（）;
T*base_arr=newT[n];
for（inti=0;ibase_arr[i]=arr[i];
msdradix_sort（base_arr,0,n-1,2）;
//-----------
finish=clock（）;
totaltime=（double）（finish-start）/CLOCKS_PER_SEC;
cout<<"运行时间：
"<cout<<"排序结果：
"<//Display（base_arr）;
}
/*----------输出函数---------*/
template
voidSortR:
:
Display（T*newarray）
{
for（inti=0;i<20;i++）
cout<cout<}
/*--------主函数-----------*/
intmain（）
{
cout<<"排序方法（从小到大）：
"<SortRmysort;
mysort.InputValue（）;
cout<<"气泡排序：
"<mysort.BubbleSort（）;
cout<<"快速排序：
"<mysort.QuickSort（）;
cout<<"插入排序：
"<mysort.InsertSort（）;
cout<<"希尔排序：
"<mysort.HillSort（）;
cout<<"选择排序：
"<mysort.SelectSort（）;
cout<<"堆排序：
"<mysort.HeapSort（）;
cout<<"归并排序：
"<mysort.MergeSort（）;
cout<<"基数排序：
"<mysort.BaseSort（）;
system（"pause"）;
return0;
}
/*
升级会员 