基础算法01

这里存放一点非常基础的算法，忘记了可以来看一眼。

主要是：排序总结，高精度总结。

排序模板

冒泡排序

这应该是最经典的排序方法，实现也很简单，也很好理解，但是时间会慢一点，复杂度是O($n^2$)

原理大概意思是比较相邻的两个数，如果他们的关系是正确的，则不做操作，如不是，则交换两个数的位置，这样从头到尾进行一次之后最大的数应该是在最后的位置，这个数就是正确顺序的，就像一个泡泡一样冒到了边缘(? 再次重复这个操作，一次完成n-1，n-2，……的排序，至此排序完成。

核心代码如下:

for (int i = 0; i < n - 1; i++)//外层循环记录要大排序次数，是数组元素数量-1
{
	for (int j = 0; j < n - i - 1; j++)//内层循环记录在一次排序下两两比较的次数，是大排序总次数减去当前排序的次数
	{
		if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
	}
}

实现较为简单，因为有两层循环的缘故，时间可能较慢，另外需要注意两次循环的边界条件

快速排序

快排是c++内置sort函数的排序方法，时间会比较快，最好的情况是O($n\log_2 n$),最坏的情况是O($n^2$),平均复杂度在O($n \log_2 n$),因此用的比较多。

原理也比较好理解:先把整个数列分成两部分，把两边的数据和中间值比较，比中间值小的放左边，反之放右边，依次操作完毕后这个中间值就是已排序状态，然后分别用同样的方法操作左右两段数据，可以看出这是根据递归定义的排序方法，在递归最底层达到条件：找不到中间值时，整段数据已经排序完毕。这里解释的不是特别全面，有一些情况可以根据代码举个例子理解。

核心代码大同小异，这里我就摆一种：

void quicksort(int l, int r)//l,r表示数组的左右两端
{
	int mid=arr[(l+r)/2];
	int i=l,j=r;
	while(i<=j)
	{
		while(arr[i]<mid) i++;
		while(arr[j]>mid) j--;
		if(i<=j)
		{
			swap(arr[i],arr[j]);
			i++;
			j--;
		}
	}
	if(l<j) quicksort(l,j);
	if(r>i) quicksort(i,r);
}

排序就先摆两个吧，有空了再贴(画饼

高精度计算

a+b高精度

高精度计算在c++中会出现是因为即使是unsigned long long型的数据最大值也就在二十位数据，也就是18446744073709551615，这样一个数据如果超过了，c++就显示不了了，会发生溢出的现象，但是在实际计算中计算大数据也不少见，因此需要用到高精度的技巧。

高精度一个很基础的想法就是数无法使用，那就使用数组，基本思路是使用字符串型读入数据，再转入数组之中进行操作。下一步可以理解为模拟竖式加法的做法，依次从个位开始对两个数字进行相加，大于10则保留个位并将十位上进一，依次操作到最后一位，并将结果数组倒序输出即可。

实现代码：

读入数组部分：

void change_arr(string a ,string b)//转换函数，熟练之后可以和相加函数结合 
{
	for(int i =0;i<a.size();i++)//转换注意需要倒序读入数组，因为相加需要进位 
	{
		arr_a[a.size()-i-1]=a[i]-48;//一次只能读入一个数组，因为两个大数字位数不一定相等
	}
	for(int i =0;i<b.size();i++)
	{
		arr_b[b.size()-i-1]=b[i]-48;//这里减去48可以换成'0' 
	}
}

计算部分：

void tooplus()
{
	int temp=max(a.size(),b.size());
	for(int i =0;i<temp;i++)
	{
		s[i]+=arr_a[i]+arr_b[i];//这里必须使用+=因为要注意前一位的进位，防止丢失数据
		s[i+1]=s[i]/10;
		s[i]%=10;//标准操作，进位且本位取最后一位数字 
	}
	if(s[temp]>0) add=1; 
}

全部代码：

#include <bits/stdc++.h>
using namespace std;
string a,b;//在long long 存储不了的情况下，基本思路是通过字符串读入，转到数组进行操作 
int arr_a[100005],arr_b[100005],s[100005],add=0;//s数组用于储存加完之后的数字 ,add用于处理进位的数字 
void change_arr(string a ,string b)//转换函数，熟练之后可以和相加函数结合 
{
	for(int i =0;i<a.size();i++)//转换注意需要倒序读入数组，因为相加需要进位 
	{
		arr_a[a.size()-i-1]=a[i]-48;//一次只能读入一个数组，因为两个大数字位数不一定相等
	}
	for(int i =0;i<b.size();i++)
	{
		arr_b[b.size()-i-1]=b[i]-48;//这里减去48可以换成'0' 
	}
}
void tooplus()
{
	int temp=max(a.size(),b.size());
	for(int i =0;i<temp;i++)
	{
		s[i]+=arr_a[i]+arr_b[i];//这里必须使用+=因为要注意前一位的进位，防止丢失数据
		s[i+1]=s[i]/10;
		s[i]%=10;//标准操作，进位且本位取最后一位数字 
	}
	if(s[temp]>0) add=1; 
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>a>>b;//读入数据，为string型
	change_arr(a,b);
	tooplus();
	for(int i =max(a.size(),b.size())+add-1;i>=0;i--)//判断输出的时候是否需要输出最终多出的一位 
	{
		cout<<s[i]; 
	}
	 return 0;
}

这里有一道例题，洛谷的p1601,可以用这个解法。

a-b高精度，a*b高精度

这两种方法基本一样，要注意的是减法有一些特殊情况，比如负数，输出长度的判断等等，这里我就摆一种简单的，乘法也是需要注意长度区别。

实现代码：

减法：

#include <bits/stdc++.h>
using namespace std;
string a,b;
bool jg;
int arr_a[100005],arr_b[10005],ans[100005],temp;
void re_input()
{
	for(int i =1;i<=a.size();i++)
	{
		arr_a[i]=a[a.size()-i]-'0';
	}
	for(int j =1;j<=b.size();j++)
	{
		arr_b[j]=b[b.size()-j]-'0';
	}
}
void to_divide()
{
	for(int i =1;i<=temp;i++)
	{
		if(arr_a[i]<arr_b[i])
		{
			arr_a[i+1]--;
			arr_a[i]+=10;
		}
		ans[i]=arr_a[i]-arr_b[i];
	}
	while(ans[temp]==0) temp--;
}
void to_printf()
{
	if(jg==true) cout<<"-";
	for(int i =temp;i>0;i--)
	{
		cout<<ans[i];
	}
	if(temp<1) cout<<"0";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>a>>b;
	if(a<b&&a.size()==b.size()||a.size()<b.size())
	{
		swap(a,b);
		jg=true;
	}
	temp=max(a.size(),b.size());
	re_input();
	to_divide();
	to_printf();
	return 0;
}

乘法：

#include <bits/stdc++.h>
using namespace std;
string a,b;
int arr01[100005],arr02[100005],sum[100005],temp=0;
void re_change()//倒序存储部分 
{
	for(int i =0;i<a.size();i++)
	{
		arr01[i]=a[a.size()-i-1]-48;
	}
	for(int i=0;i<b.size();i++)
	{
		arr02[i]=b[b.size()-i-1]-48;
	}
}
void mutiply()
{
	for(int i =0;i<b.size();i++)
	{
		for(int j =0;j<a.size();j++)
		{
			sum[i+j]+=arr01[j]*arr02[i];//注意下标从1开始，进位减去1 
		}
	}
	for(temp =0;temp<=a.size()+b.size();temp++)//处理进位 
	{
		
		sum[temp]+=sum[temp-1]/10;
		sum[temp-1]%=10;
		
	}
	//temp=a.size()+b.size();
	while(sum[temp]==0&&temp>=1)
	{
		temp--;
	}
	
 } 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>a>>b;
	re_change();
	mutiply();
	for(;temp>=0;temp--)
	{
		cout<<sum[temp];
	}
	
	return 0;
}