快排+高精度
2023-08-20 15:46:11
发布于：河北
7阅读
0回复
0点赞
快速排序算法模板
void quick_sort(int q[], int l, int r) //qsort
{
if (l >= r) return;
//分两部分
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
//递归调用
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
归并排序算法模板
- 归并归并，先归再并
int tmp[N]; //需要额外临时数组
void merge_sort(int q[], int l, int r) // merge合并 msort()
{
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ];
while (i <= mid)
{
tmp[k ++ ] = q[i ++ ];
}
while (j <= r)
{
tmp[k ++ ] = q[j ++ ];
}
for (i = l, j = 0; i <= r; i ++, j ++ )
{
q[i] = tmp[j];
}
}
先分，后递归
快排核心思想：前面小的，后面大的，两部分
高精度算法核心：
c[i]+=a[i]+b[i];
c[i+1]=c[i]/10;
c[i]=c[i]%10;
代码：
加法（方法一）：
#include<bits/stdc++.h>
using namespace std;
const int N=520;
int a[N],i1,b[N],i2,c[N];
int main()
{
string s1,s2;
cin>>s1>>s2;
int len1 = s1.size();
int len2 = s2.size();
//1.逆序转换数组
for(int i=len1-1; i>=0; i--)
{
a[i1++] = s1[i]-'0';
}
for(int i=len2-1; i>=0; i--)
{
b[i2++] = s2[i]-'0';
}
//2.计算
int len=max(len1,len2);
for(int i=0; i<len; i++)
{
c[i]+=a[i]+b[i];
c[i+1]=c[i]/10;
c[i]=c[i]%10;
}
//3.逆序输出
if(c[len]!=0)
{
cout<<c[len];
}
for(int i=len-1;i>=0;i--)
{
cout<<c[i];
}
return 0;
}
加法（方法二）：
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s1,s2;
cin>>s1>>s2;
//1.逆序数组
vector<int> a;
vector<int> b;
for(int i=s1.size()-1; i>=0; i--)
{
a.push_back(s1[i]-'0');
}
for(int i=s2.size()-1; i>=0; i--)
{
b.push_back(s2[i]-'0');
}
//2.计算
int n=max(a.size(),b.size())+1;
vector<int>c;
int t = 0;
for(int i=0; i<n; i++)
{
if(i < a.size()) t += a[i];
if(i < b.size()) t += b[i];
c.push_back(t % 10);
t /= 10;
}
if(t)c.push_back(t);
//3.逆序输出
for(int i=c.size()-1; i>=0; i--)
{
cout << c[i];
}
return 0;
}
这里空空如也
有帮助，赞一个