c++各种排序算法实现
发布日期:2022-02-21 17:40:30 浏览次数:29 分类:技术文章

本文共 3599 字,大约阅读时间需要 11 分钟。

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;//含有跳跃式交换的排序算法,都是不稳定的算法//---------交换类-------//冒泡排序---稳定的排序、最好n、平均n^2、最坏n^2bool bubblesort(int a[],int n){
       
if(a==NULL)
return false;
bool btmp;
for(int i=n-1;i>0;i--)
{
btmp=false;
for(int j=0;j
{
if(a[j+1]
{
int tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
btmp=true;
}
}
if(btmp==false) return true;//最好的情况是,已经排好序,然后没有交换则跳出
}
return false;}//冒泡法改进版----记住最后一次交换的位置,减少第一次循环的次数bool bubblehigh(int a[],int n){
if(a==NULL)
return false;
int i=n-1;
int j=0;
bool btmp=true;
int aus=0;
while(i>0&&btmp)
{
btmp=false;
for(j=0;j
{
if(a[j]>a[j+1])
{
int tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
btmp=true;
aus=j;
}
}
i=j;
if(btmp==false) return true;
}
return true;}//快排----不稳定的排序、最好nlgn、平均nlgn、最坏n^2(不能够进行二分)void quicksort(int a[],int le,int rg){
if(le>=rg) return;
int left=le;
int right=rg;
int mid=a[left];
while(left
{
while(left <=a[right])
right--;
if(left
while(left <=mid)
left++;
if(left
}
a[left]=mid;
quicksort(a,le,right-1);
quicksort(a,right+1,rg);}//------插入类-----//直接插入排序,稳定排序,最好时间复杂度n(已经排好的),平均复杂度n^2,最坏n^2bool insertsort(int a[],int n){
if(a==NULL)
return false;
for(int i=1;i
{
int j=i-1;
int tmp=a[i];
while(j>=0&&tmp
{
a[j+1]=a[j];
j--;
}
a[j+1]=tmp;
}
return true;}//折半插入排序,改变不了时间复杂度bool halfsort(int a[],int n){
if(a==NULL)
return false;
for(int i=1;i
{
int tmp=a[i];
int left=0;
int right=i;
while(left<=right)
{
int mid=(left+right)/2;
if(tmp<=a[mid])
right=mid-1;
else
left=mid+1;
}
int j=0;
for(j=i-1;j>=left;j--)
a[j+1]=a[j];
a[j+1]=tmp;
}
return true;}//增量排序--不稳定的排序,最差复杂度n^2,最好nlgn,平均n1.3bool shellsort(int a[],int n){
if(a==NULL) return false;
int d=n/2;
while(d>=1)
{
for(int i=0;i
{//插入排序
for(int j=i;j
{
int tmp=a[j];
int k=j-d;
while(k>=i&&a[k]>tmp)///注意这里是k>i
{
a[k+d]=a[k];
k=k-d;
}
a[k+d]=tmp;
}
}
d=d/2;
}
return true;}//-------选择类----//直接选择排序,时间复杂度最好n^2,平均n^2,最坏n^2//例如8* 3 5 4 8 3 1 9 并不稳定bool selectsort(int a[],int n){
if(a==NULL)
return false;
for(int i=0;i
{
int minplace=i;
for(int j=i;j
{
if(a[j]
minplace=j;
}
int tmp=a[i];
a[i]=a[minplace];
a[minplace]=tmp;
}
return true;}//堆排(这里排成了最大堆)----不稳定算法 时间复杂度最坏nlgn 平均nlgn 最好nlgn(二分)void adjustsort(int a[],int start,int end)//start为下标,end为长度{
int dad=start;
int son=2*dad+1;
while(son
{
if((son+1)
son++;
if(a[son]>a[dad]) 
{
 
int tmp=a[son];
a[son]=a[dad];
a[dad]=tmp;
dad=son;
son=2*son+1;
}
else
return;
}}bool heapsort(int a[],int n){
if(a==NULL) return false;
for(int i=(n/2)-1;i>=0;i--)
adjustsort(a,i,n);
for(int i=n-1;i>=0;i--)
{
int tmp=a[i];
a[i]=a[0];
a[0]=tmp;
adjustsort(a,0,i);
}
return true;}//归并排序void merge(int a[],int le,int mid,int rg){
int l=le;
int r=mid+1;//
int tmp[rg-le+1];
vector  tmp;
while(l<=mid&&r<=rg)
{
if(a[l]
tmp.push_back(a[l++]);
else
tmp.push_back(a[r++]);
}
while(r<=rg)
tmp.push_back(a[r++]);
while(l<=mid)
tmp.push_back(a[l++]);
int k=le;
int len=tmp.size();
for(int i=0;i
a[k]=tmp[i];}void mergesort(int a[],int left,int right){
if(a==NULL) return ;
if(left==right) return ;
int mid=(left+right)/2;
mergesort(a,left,mid);
mergesort(a,mid+1,right);
vector  tmp;
merge(a,left,mid,right);}int main(){
int a[]={5,4,7,3,2,8,6,1};
int n=sizeof(a)/sizeof(int);
//bool res=bubblesort(a,n);
//bool res=bubblehigh(a,n);
//quicksort(a,0,n-1);
//bool res=insertsort(a,n);
//bool res=halfsort(a,n);
//bool res=shellsort(a,n);
//bool res=selectsort(a,n);
//bool res=heapsort(a,n);
mergesort(a,0,n-1);
cout<<"排序后结果:";
for(int i=0;i<8;i++)
{
cout< <<" ";
}
cout<
system("pause");}

还有: 桶排序和基数排序

效率比较:

转载地址:https://blog.csdn.net/weixin_40599276/article/details/100838430 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:写一个完整的memcpy,strcpy,strlen char *a = "aa"; char s[] = "123456789"; char d[] = "123"; st
下一篇:Netty | 01 - 服务器启动流程以及常用api笔记

发表评论

最新留言

感谢大佬
[***.46.13.205]2022年12月04日 12时19分17秒