排序算法-1---AngelNH

记住一切都会好起来。给他一点时间。

排序一共有十种排序算法，虽然都没有Algorithm的sort简单好用，但多学无害。

如果你对代码理解起来比较难，你可以参考这篇博文，介绍了十种排序算法排序的动画演示GIF

下面就看是介绍比较简单的三种排序算法，分别是冒泡排序，选择排序，计数排序，简单插入排序，折半插入排序，希尔排序，快速排序，话不多说，上代码。

冒泡排序

冒泡排序有两种方法，一种是最原始的，还有一种是改进过的。

#include<iostream> using namespace std; typedef long long ll; #define rep(i,x,y) for(ll i =x;i<=y;++i) #define MAX 1000000 ll a[MAX],n; inline void swap(ll i ,ll j) { ll t = a[i]; a[i] = a[j]; a[j] = t; } //ordinary sort inline void bubblesort(ll a[])// { for(ll i=1;i<n;++i) { for(ll j =n-1;j>=i;--j) // for(ll j =1;i<=n-j;++j) { if(a[j]>a[j+1]) { swap(j,j+1); } } } } //Optimized sort inline void bubblesort_1(ll a[]) { int flag =1; for(ll i =1;i<n&&flag;++i) { flag = 0; for(ll j = n-1;j>=i;--j ) { if(a[j]>a[j+1]) { swap(j,j+1); flag = 1; } } } } int main() { cout<<"please input the size of the data："<<endl; while(cin>>n) { ll i; rep(i,1,n) { cin>>a[i]; } //two measures of sorting data //first //bubblesort(a); //second bubblesort_1(a); rep(i,1,n) { cout<<a[i]<<" "; } cout<<endl; cout<<"Please input the size of the data:"<<endl; } return 0; }选择排序#include<iostream> using namespace std; typedef long long ll; ll a[10000],n; inline void swap(ll i,ll j) { ll t = a[i]; a[i] = a[j]; a[j] = t; } inline void selectsort(ll a[]) { ll k,t; for(ll i =1;i<n;++i) { k =i; for(ll j =i+1;j<=n;++j) { if(a[j]>a[k]) k = j; } if(k!=i) { swap(k,i); } } } int main() { while(cin>>n) { for(ll i=1;i<=n;++i) { cin>>a[i]; } selectsort(a); //select_sort(a); for(ll i =1;i<=n;++i) { cout<<a[i]<<" "; } cout<<endl; } return 0; }计数排序#include<iostream> #include<stdlib.h> #include<time.h> using namespace std; //bilibili //https://www.bilibili.com/video/av54557540/?spm_id_from=333.788.videocard.1 int a[10000]; void getarray(int *a,int n) { //unsigned sr = time(NULL); int t=1000; srand(time(NULL)); while(t<1||t>100) { for(int i=0;i<n;++i) { t=rand()%100; a[i] = t; } } cout<<"Random array is: "<<endl; for(int i =0;i<n;++i) cout<<a[i]<<" "; cout<<endl; } void countsort(int *A,int *Aux,int *sortedA,int n) { int k =0; for(int i=0;i<n;++i) { k = max(k,A[i]); } for(int i=0;i<k;++i) { Aux[i] = 0; } for(int i=0;i<n;++i) { Aux[A[i]]++; } int j =0; for(int i=0;i<=k;++i) { int t = Aux[i]; while(t--) { sortedA[j] = i; j++; } } } int main() { int n; cout<<"请输入数量"<<endl; while(cin>>n) { getarray(a,n); int b[10000],c[1000]; countsort(a,b,c,n); cout<<"排序结果为：n"; for(int i =0;i<n;++i) cout<<c[i]<<" "; cout<<endl; cout<<"请输入数量"<<endl; } return 0; }简单插入排序#include<iostream> using namespace std; #define MAX 100000 #define rep(i,x,y) for(int i =x;i<=y;++i) typedef long long ll; typedef struct { ll aa; }data; typedef struct { data a[MAX]; ll length; }List; void insertsort(List &L) { ll i,j; rep(i,2,L.length) { if(L.a[i].aa<L.a[i-1].aa) { L.a[0] = L.a[i]; L.a[i] = L.a[i-1]; for( j =i-2;L.a[0].aa<L.a[j].aa;--j) { L.a[j+1] = L.a[j]; } L.a[j+1] = L.a[0]; } } } int main() { int n; List L; cout<<"请输入数据大小"<<endl; while(cin>>n) { ll i; L.length = n; rep(i,1,n) { cin>>L.a[i].aa; } insertsort(L); rep(i,1,n) { cout<<L.a[i].aa<<" "; } cout<<endl; cout<<"请输入数据大小"<<endl; } return 0; }折半插入排序#include<iostream> using namespace std; typedef long long ll; #define MAX 10000 #define rep(i,x,y) for(int i =x;i<=y;++i) typedef struct { ll aa; }data; typedef struct { data a[MAX]; ll length; }List; void binary_insert_sort(List &L) { ll i; ll low,high,m; rep(i,2,L.length) { L.a[0] = L.a[i]; low = 1;high = i-1; while(low<=high) { m = (low+high)/2; if(L.a[0].aa<L.a[m].aa) high = m-1; else low = m+1; } for(ll j = i-1;j>=high+1;--j) L.a[j+1] = L.a[j]; L.a[high+1] = L.a[0]; } } int main() { int n; List L; cout<<"请输入数据大小"<<endl; while(cin>>n) { ll i; L.length = n; rep(i,1,n) { cin>>L.a[i].aa; } binary_insert_sort(L); rep(i,1,n) { cout<<L.a[i].aa<<" "; } cout<<endl; cout<<"请输入数据大小"<<endl; } return 0; }希尔排序#include<iostream> using namespace std; typedef long long ll; ll n,a[10000]; inline void shellsort(ll a[]) { int t; for(int gap = n/2;gap>0;gap/=2) { for(int i=gap;i<n;++i) { for(int j = i-gap;j>=0&&a[j]>a[j+gap];j-=gap ) { t = a[j]; a[j] = a[j+gap]; a[j+gap] = t; } } } } int main() { cout<<"请输入数据大小"<<endl; while(cin>>n) { for(int i =0;i<n;++i) { cin>>a[i]; } shellsort(a); for(int i =0;i<n;++i) { cout<<a[i]<<" "; } cout<<endl; cout<<"请输入数据大小"<<endl; } return 0; }快速排序#include<iostream> using namespace std; typedef long long ll; ll n,a[100000]; inline ll partition(ll a[],ll begin,ll end) { a[0] = a[begin]; ll key = a[begin]; while(begin<end) { while(begin<end&&a[end]>=a[0]) end--; a[begin] = a[end]; while(begin<end&&a[begin]<=a[0]) begin++; a[end] = a[begin]; } a[end] = a[0]; return end; } inline void quicksort(ll a[],ll begin, ll end) { if(begin<end) { ll pivotkey = partition(a,begin,end); quicksort(a,begin,pivotkey-1); quicksort(a,pivotkey+1,end); } } int main() { cout<<"Please input the size of the data"<<endl; while(cin>>n) { for(ll i=1;i<=n;++i) { cin>>a[i]; } quicksort(a,1,n); for(ll i=1;i<=n;++i) { cout<<a[i]<<" "; } cout<<endl; cout<<"Please input the size of the data"<<endl; } return 0; } ---来自腾讯云社区的---AngelNH