排序算法
第一种:选择排序
第二种:冒泡排序、改进冒泡排序
第三种:插入排序
第四种:快速排序
第五种:归并排序
#include<iostream> #include<cstring> using namespace std; const int MAXN=1000; int a[MAXN]; int n; //选择排序 void xuanze(){ int k; for(int i=0;i<n;i++){ k=i; for(int j=i+1;j<n;j++) if(a[j]<a[k]) k=j; //注意是a[j]<a[[k] if(k!=i) { swap(a[i],a[k]); } } cout<<"选择排序如下: "; for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; } //冒泡排序 void maopao(){ for(int i=n-1;i>=1;i--){ for(int j=0;j<i;j++){ if(a[j]>a[j+1]) swap(a[j],a[j+1]); } } cout<<"冒泡排序如下: "; for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; } //改进冒泡排序 void impmaopao(){ bool ok; for(int i=n-1;i>=1;i--){ ok=true; for(int j=0;j<i;j++){ if(a[j]>a[j+1]) { swap(a[j],a[j+1]); ok=false; } } if(ok==true) break; } cout<<"改进冒泡排序如下: "; for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; } //插入排序 void charu(){ int temp=0,k,i,j; for( i=1;i<n;i++){ for(j=i-1;j>=0;j--){ if(a[j]<a[i]) break; } if(j!=i-1){ temp=a[i]; for(k=i-1;k>j;k--) a[k+1]=a[k]; a[k+1]=temp; } } cout<<"插入排序如下: "; for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; } //快速排序 void qsort(int l,int r){ int i,j,mid; i=l;j=r; mid=a[(l+r)/2]; do{ while(a[i]<mid) i++; while(a[j]>mid) j--; if(i<=j){ swap(a[i],a[j]); i++;j--; } }while(i<=j); if(l<j) qsort(l,j); if(i<r) qsort(i,r); } //归并排序 int r[MAXN];//辅助数组 int ans=0; //逆序数 void msort(int s,int t){ if(s==t) return; //只有一个元素时不需要比较 int mid=(s+t)/2; msort(s,mid); //分解左序列 msort(mid+1,t); //分解右序列 int i=s,j=mid+1,k=s; //合并,注意k的初始值不是为0 while(i<=mid&&j<=t){ if(a[i]<=a[j]) r[k++]=a[i++]; else { r[k++]=a[j++]; ans+=mid-i+1; } } while(i<=mid) r[k++]=a[i++]; while(j<=t) r[k++]=a[j++]; for(int i=s;i<=t;i++) a[i]=r[i]; //注意i的起始和终止值 } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; //快速排序和归并排序从i=1开始 //xuanze(); //maopao(); //impmaopao(); //charu(); /*qsort(1,n); cout<<"快速排序如下: "; for(int i=1;i<=n;i++) cout<<a[i]<<" "; cout<<endl; */ msort(1,n); cout<<"归并排序如下: "; for(int i=1;i<=n;i++) cout<<a[i]<<" "; cout<<endl; return 0; }
第六种:桶排序
第七种:堆排序(基本的堆的操作)
#include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<cstdio> #include<queue> using namespace std; //堆排序 //小根堆 int n,heap[100001]; //堆调整 void heapadjust(int x,int high){ //后面的high必须要有 int i=x,j=2*i; while(j<=high){ if((j+1<=high)&&heap[j]>heap[j+1]) j++; if(heap[j]<heap[i]){ swap(heap[i],heap[j]); i=j; j=2*i; } else break; } } //删除堆顶元素 int delete(){ int ans=heap[1]; heap[1]=heap[n--]; heapadjust(1,n); return ans; } //添加堆顶元素 void insert(int x){ heap[++n]=x; heapadjust(1,n);//向上调整新加入的节点 } //建堆 void heapsort(){ for(int i=n/2;i>=1;i--) heapadjust(i,n); //建立一个初始小根堆 for(int i=n;i>1;i--){ swap(heap[1],heap[i]); //将最后一个与第一个交换,最小值到了最后 heapadjust(1,i-1); } } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>heap[i]; heapsort(); for(int i=n;i>1;i--) cout<<heap[i]<<" "; cout<<heap[1]<<endl; return 0; }
相关推荐
hang0 2020-08-16
风吹夏天 2020-07-07
小海 2020-06-25
清溪算法君老号 2020-06-06
wonner 2020-06-03
清溪算法君老号 2020-06-01
randy0 2020-11-17
lixiaotao 2020-10-07
美丽的泡沫 2020-09-08
nongfusanquan0 2020-08-18
earthhouge 2020-08-15
算法改变人生 2020-07-28
troysps 2020-07-19
Broadview 2020-07-19
chenfei0 2020-07-18
yangjingdong00 2020-07-05
数据与算法之美 2020-07-05