常用六大排序算法的实现
非原创，协会里爬的
插入排序(insertion_sort)
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
// 插入排序
void insertion_sort(vector<int>& a)
{
for(int i=0;i<a.size();i++)// 从第一个开始做插入
{
int t=a[i],j;// 存储数据
for(j=i-1;j>=0;j--)// 从前一个数开始作比较
if(t<a[j]) a[j+1]=a[j]; // 若前一个数比当前数大，则后一个数放前一个数
else break;// 否则退出
a[j+1]=t; // 后一个数放存储的数值，这个插入操作必须放在循环外面
}
}
int main()
{
int n;
vector<int> a;
cin>>n;
for(int i=0,t;i<n;i++)
{
cin>>t;
a.push_back(t);
}
insertion_sort(a);
for(int i=0;i<n;i++)cout<<a[i]<<" ";
return 0;
}
堆排序(heap_sort)
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,m;
vector<int> heap;
// 从小到大排序建大根堆，因为根节点要放到最后面
// 从大到小排序建小根堆
//堆中，默认下标0弃置，下标1的元素为根节点
//大根堆，下沉操作
void push_down(vector<int>& heap,int size,int u)
{
int t=u,left=u*2,right=u*2+1;
if(left<=size && heap[left]>heap[t])t=left;//不越界，并且左子树较大
if(right<=size && heap[right]>heap[t])t=right;//不越界，并且右子树较大
if(t!=u)//如果存在更大的值
{
swap(heap[u],heap[t]);//交换
push_down(heap,size,t);//下沉
}
}
//大根堆，上浮操作
void push_up(vector<int>& heap,int u)
{
while(u/2 && heap[u/2]<heap[u])//如果没有越界，并且父节点更小
{
swap(heap[u/2],heap[u]);//交换
u/=2;//上移
}
}
//堆排序
void heap_sort(vector<int>& heap,int size)
{
int n=size;
for(int i=1;i<=n;i++)push_up(heap,i);//建堆，像插入一样、上浮
//堆排序
for(int i=1;i<=n;i++)//排序n次
{
swap(heap[1],heap[size]);//将根节点（最大的数）放到最后面
size--;//数量--
push_down(heap,size,1);
}
}
int main()
{
cin>>n>>m;
heap.resize(n+1);
for(int i=1;i<=n;i++)cin>>heap[i];
heap_sort(heap,n);//排序堆中的前n个数
for(int i=1;i<=m;i++)cout<<heap[i]<<' ';
return 0;
}
归并排序(merge_sort)
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
void merge_sort(vector<int>& a,int l,int r)
{
if(l>=r)return;//此处的=号可以解决边界问题
int mid=(l+r)/2; // 去中间值
merge_sort(a,l,mid);//递归
merge_sort(a,mid+1,r);
static vector<int> st;
st.clear();
int i=l,j=mid+1;
while(i<=mid && j<=r)//归并
if(a[i]<a[j])st.push_back(a[i++]);
else st.push_back(a[j++]);
//处理剩余元素
while(i<=mid)st.push_back(a[i++]);
while(j<=r)st.push_back(a[j++]);
// 此处建议像如下一样，采用双指针的写法
for(i=0,j=l;i<st.size();i++,j++)a[j]=st[i];//覆盖
}
int main()
{
int n;
vector<int> a;
cin>>n;
for(int i=0,t;i<n;i++)
{
cin>>t;
a.push_back(t);
}
merge_sort(a,0,a.size()-1);
for(int i=0;i<n;i++)cout<<a[i]<<" ";
return 0;
}
快速排序(quick_sort)
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
// 快速排序
void quick_sort(vector<int>& a,int l,int r)
{
if(l>=r)return;
int i=l-1,j=r+1,x=a[(l+r)>>1];//x可以是一个随机数，此处选择中间的数
while(i<j)
{
do i++;while(a[i]<x);//此处是一个双指针
do j--;while(a[j]>x);
if(i<j)swap(a[i],a[j]);//交换
else quick_sort(a,l,j),quick_sort(a,j+1,r);//递归,此处参数必须是 j
}
}
int main()
{
int n;
vector<int> a;
cin>>n;
for(int i=0,t;i<n;i++)
{
cin>>t;
a.push_back(t);
}
quick_sort(a,0,a.size()-1);
for(int i=0;i<n;i++)cout<<a[i]<<" ";
return 0;
}
冒泡排序(bubble_sort)
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> a;
// 冒泡排序
void bubble_sort(vector<int>& a)
{
bool f=false;//交换标记
for(int i=a.size()-1;i>0;i--)//可以比较的最后一个数
{
for(int j=0;j+1<=i;j++)//从0开始，比较到最后一个数
if(a[j]>a[j+1])
{
swap(a[j],a[j+1]);
f=true;
}
if(f==false)return;//不存在交换，说明已经排好序了，直接返回，这是一个小优化
}
}
int main()
{
int n;
cin>>n;// 输入
for(int i=0,t;i<n;i++)
{
cin>>t;
a.push_back(t);
}
bubble_sort(a);
// 输出
for(int i=0;i<n;i++)cout<<a[i]<<" ";
return 0;
}
选择排序(selection_sort)
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
//选择排序
void selection_sort(vector<int>& a)
{
for(int i=0;i<a.size();i++)// 选择第i个数
for(int j=i+1;j<a.size();j++)// 和第j个数比较
if(a[j]<a[i])// 若比第i个数小，交换两个数
swap(a[i],a[j]);
}
int main()
{
int n;
vector<int> a;
cin>>n;
for(int i=0,t;i<n;i++)
{
cin>>t;
a.push_back(t);
}
selection_sort(a);
for(int i=0;i<n;i++)cout<<a[i]<<" ";
return 0;
}
高精度
高精度-乘法
#include<iostream>
#include<string>
#include<vector>
using namespace std;
//一个大数A * 一个正常int型整数B
int main()
{
string a;
int b;
cin>>a>>b;
vector<int> A;
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
vector<int> C;
for(int i=0,t=0;i<A.size()||t;i++)
{
if(i<A.size())t+=A[i]*b;//此处和加法类似
C.push_back(t%10);
t/=10;
}
while(C.size()>1 && C.back()==0)C.pop_back();
for(int i=C.size()-1;i>=0;i--)cout<<C[i];
return 0;
}
高精度-除法
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
string a;
int b;
cin>>a>>b;
vector<int> A;
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
vector<int> C;
for(int i=A.size()-1,t=0;i>=0;i--)
{
t*=10;
t+=A[i];
C.push_back(t/b);
t%=b;
}
while(C.size()>1 && C.front()==0)C.erase(C.begin());//ČĽłýÇ°ľź0
for(int i=0;i<C.size();i++)cout<<C[i];
return 0;
}
高精度-加法
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
string a,b;
vector<int> A,B;
cin>>a>>b;
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');//前面是低位,后面是高位
for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');
vector<int> C;
for(int i=0,t=0;i<A.size() || i<B.size() || t;i++)
{
if(i<A.size())t+=A[i];
if(i<B.size())t+=B[i];
C.push_back(t%10);
t/=10;
}
for(int i=C.size()-1;i>=0;i--)cout<<C[i];
return 0;
}
高精度-减法
#include<iostream>
#include<string>
#include<vector>
using namespace std;
const int N=1000010;
typedef vector<int> vec;
bool cmp(vec& A,vec& B)//判断A是否大于B
{
if(A.size()!=B.size())return A.size()>B.size();
for(int i=A.size()-1;i>=0;i--)//后面是高位
if(A[i]!=B[i])
return A[i]>B[i];
return true;//两数相等
}
vec sub(vec& A,vec& B)// C=A-B 满足 A>B , A>0 , B>0
{
vec C;
for(int i=0,t=0;i<A.size();i++)
{
t=A[i]-t;//加上A[i],减去借位
if(i<B.size())t-=B[i];
C.push_back((t+10)%10);// 2-5=-3 -> 12-5=7
if(t<0)t=1;//t<0代表有借位
else t=0;
}
while(C.size()>1 && C.back()==0)C.pop_back();//去除前导零
return vec(C.rbegin(),C.rend());//翻转
}
int main()
{
string a,b;
vector<int> A,B;
cin>>a>>b;
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');
vector<int> C;
if(cmp(A,B))C=sub(A,B);
else C=sub(B,A);
for(int i=0;i<C.size();i++)cout<<C[i];
return 0;
} xxxxxxxxxx #include<iostream>#include<string>#include<vector>using namespace std;const int N=1000010;typedef vector<int> vec;bool cmp(vec& A,vec& B)//判断A是否大于B { if(A.size()!=B.size())return A.size()>B.size(); for(int i=A.size()-1;i>=0;i--)//后面是高位 if(A[i]!=B[i]) return A[i]>B[i]; return true;//两数相等 } vec sub(vec& A,vec& B)// C=A-B 满足 A>B , A>0 , B>0 { vec C; for(int i=0,t=0;i<A.size();i++) { t=A[i]-t;//加上A[i],减去借位 if(i<B.size())t-=B[i]; C.push_back((t+10)%10);// 2-5=-3 -> 12-5=7 if(t<0)t=1;//t<0代表有借位 else t=0; } while(C.size()>1 && C.back()==0)C.pop_back();//去除前导零 return vec(C.rbegin(),C.rend());//翻转} int main(){ string a,b; vector<int> A,B; cin>>a>>b; for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0'); for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0'); vector<int> C; if(cmp(A,B))C=sub(A,B); else C=sub(B,A); for(int i=0;i<C.size();i++)cout<<C[i]; return 0;}
双高精度-乘法
#include<iostream>
#include<string>
#include<vector>
using namespace std;
const int N=1000010;
typedef vector<int> vec;
bool cmp(vec& A,vec& B)//判断A是否大于B
{
if(A.size()!=B.size())return A.size()>B.size();
for(int i=A.size()-1;i>=0;i--)//后面是高位
if(A[i]!=B[i])
return A[i]>B[i];
return true;//两数相等
}
vec sub(vec& A,vec& B)// C=A-B 满足 A>B , A>0 , B>0
{
vec C;
for(int i=0,t=0;i<A.size();i++)
{
t=A[i]-t;//加上A[i],减去借位
if(i<B.size())t-=B[i];
C.push_back((t+10)%10);// 2-5=-3 -> 12-5=7
if(t<0)t=1;//t<0代表有借位
else t=0;
}
while(C.size()>1 && C.back()==0)C.pop_back();//去除前导零
return vec(C.rbegin(),C.rend());//翻转
}
int main()
{
string a,b;
vector<int> A,B;
cin>>a>>b;
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');
vector<int> C;
if(cmp(A,B))C=sub(A,B);
else C=sub(B,A);
for(int i=0;i<C.size();i++)cout<<C[i];
return 0;
}
双高精度-除法(滚动减法模拟除法)
#include<iostream>
#include<string>
#include<vector>
using namespace std;
typedef vector<int> vec;
int cmp(vec A,vec B)//比较大小 > = < 对应 1 0 -1
{
if(A.size()!=B.size())
if(A.size()>B.size())return 1;
else return -1;
for(int i=0;i<A.size();i++)
if(A[i]!=B[i])
if(A[i]>B[i])return 1;
else return -1;
return 0;
}
vec sub(vec A,vec B)//减法
{
A=vec(A.rbegin(),A.rend());
B=vec(B.rbegin(),B.rend());
vec C;
for(int i=0,t=0;i<A.size();i++)
{
t=A[i]-t;
if(i<B.size())t-=B[i];
C.push_back((t+10)%10);
if(t<0)t=1;
else t=0;
}
while(C.size()>1 && C.back()==0)C.pop_back();
return vec(C.rbegin(),C.rend());
}
pair<vec,vec> div(vec A,vec B)//滚动减法模拟除法
{
int initsize=B.size();//记录除数的初始位数
while(A.size()>B.size())B.push_back(0);//除数扩大到极限
vec C;
while(1)
{
int t=0;//减的次数
for(t=0;cmp(A,B)>=0;t++)A=sub(A,B);//A>=B就减
C.push_back(t);
if(B.size()==initsize)break;//到达除数本身,除法结束
else B.pop_back();//除数%10
}
while(C.size()>1 && C.front()==0)C.erase(C.begin());//去除前导0
return pair<vec,vec>(C,A);//返回结果
}
int main()
{
string a,b;
cin>>a>>b;
vector<int> A,B;
for(int i=0;i<a.size();i++)A.push_back(a[i]-'0');
for(int i=0;i<b.size();i++)B.push_back(b[i]-'0');
pair<vec,vec> C;
C=div(A,B);//A除B,返回值为 商和余
vec t=C.first;//输出
for(int i=0;i<t.size();i++)cout<<t[i];
cout<<endl;
t=C.second;
for(int i=0;i<t.size();i++)cout<<t[i];
return 0;
}