[数据结构与算法]快排、归并、二分、高精度加、减法

排序：快排，归并

二分：整数，浮点数

有单调性一定可以二分

浮点数二分

和整数二分类似，当区间 L ~ R 长度很小时( ≤ 10^-6)，可认为找到了答案，用 L 或者 R 当做答案

输入一个数 x，求平方根

如果题目要求保留四位小数：e-6? 保留五位小数：e-7 保留六位小数：e-8

要比要求的有效位数多 2

注意：如果所求的数小于 1，需要把右边界 + 1

#include<iostream>
#include<cstdio> 
using namespace std;

int main()
{
	double x;
	cin >> x;
	double l = 0, r = x;
	if (x < 1) r += 1;
	while (r - l > 1e-8)
	{
		double mid = (l + r) / 2;
		if (mid * mid >= x) r = mid;
		else l = mid;
	}

	printf("%lf", l);
	getchar();
    return 0;
}

不用精度来表示迭代，直接循环 100 次也可以

#include<iostream>
#include<cstdio> 
using namespace std;

int main()
{
	double x;
	cin >> x;
	double l = 0, r = x;
	for(int i=0;i<100;i++)
	{
		double mid = (l + r) / 2;
		if (mid * mid >= x) r = mid;
		else l = mid;
	}

	printf("%lf", l);
	getchar();
    return 0;
}

快排

基于分治

假设区间为 L ~ R

①确定分界点x：取左边界q[L]、q[(L+R)/2]、取右边界q[R]、随机

②调整区间：左半边区间的数都 ≤ x ，右半边区间的数都 ≥ x，分界点的数不一定是 x

③递归处理左右两段

左、右两边排好序后，整个区间就是有序的

左边的最大值小于右边的最小值

实现方式 1：

排序算法 --- 二分查找、快排、归并、分治思想_考拉爱睡觉鸭~的博客-CSDN博客

实现方式 2：

①开两个额外的数组 a[ ]、b[ ]

②遍历 q[L~R]，如果当前的数 ≤ x，把它插入a[ ]，如果当前的数 ≥ x，把它插入b[ ]

③先把a[ ]的数放入q[ ]，再把b[ ]中的数放到q[ ]

a[ ]的数都 ≤ x，b[ ]的数都 ≥ x

#include<iostream>
using namespace std;
const int N=1e6+10;
int n;
int q[N];
void quick_sort(int q[],int l,int r)
{
	if(l>=r) return;
	int x=q[l],i=l-1,j=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 main()
{
 	scanf("%d",&n);
 	for(int i=0;i<n;i++) scanf("%d",&q[i]);
 	quick_sort(q,0,n-1);
 	for(int i=0;i<n;i++) printf("%d",q[i]);
 	return 0;
}

归并

①确定分界点 mid = (left + right) / 2

②递归排序 left、right

③归并 把两个有序数组合并成一个有序数组

#include<iostream>
#include<cstdio> 
using namespace std;
const int N = 100010; 
int n;
int q[N],tmp[N];
void merge_sort(int q[],int l,int r)
{
	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];
}
int main()
{
	scanf("%d",&n);
	for(int i = 0;i < n;i++) scanf("%d",&q[i]);
	merge_sort(q,0,n-1);
	for(int i = 0;i < n;i++) printf("%d ",q[i]);
	getchar();
	return 0;
}

高精度加法

两个较大的整数相加(位数：10^6)

两个较大的整数相减(位数：10^6)

一个大整数 A ( 位数：A ≤ 10^6，数值：a < 10000)乘一个小整数 a

A 除以 B 求商和余数

大整数的存储

把大整数的每一位存到数组中(有一个大整数123456789，选择高位在前还是低位在前)

加减乘除中大整数的存储都是一致的

数字：??????? 1??? 2??? 3??? 4??? 5??? 6??? 7??? 8??? 9

数组下标：[0]? [1]? [2]? [3]? [4]? [5]? [6]? [7]? [8]

存储：??????? 9??? 8??? 7??? 6??? 5??? 4??? 3??? 2??? 1

选择低位在前，下标为 [0] 的位置存个位，下标为 [1] 的位置存十位. . .

做整数相加，相乘可能会进位，需要在高位补上一个数，只需要在数组末尾补上一个数即可，如果想在数组开头补上一个数，需要把整个数组全部往后平移一位

模拟加法：先把两个数组的个位相加，十位相加. . .

??????? A3??????? A2??????? A1??????? A0
?? +?????????????? B2??????? B1??????? B0
?????? ————————————
?? ?? ? ? ? ? ? ? ? C2?? ??? C1??????? C0

A0 + B0 大于十进一位，小于十不进位 →? (A0+B0) % 10 == C0

A1 + B1 + t (上一位的进位) == C1 ???????????????

没有进位：0??? 有进位

一般多开 10 个空间，防止出现边界问题：const int N = 1 e6 + 10；

#include<iostream>
#include<cstdio> 
#include<vector>
using namespace std;

//C = A + B 
vector<int> add(vector<int> &A, vector<int> &B)
{
	//存储结果 
	vector<int> C;
	//用于进位-> 第0位没有进位
	int t = 0;
	//从个位开始遍历-> 只要A或B没有遍历完就一直遍历 A0+B0,A1+B1...
	for(int i=0;i<A.size()||i<B.size();i++)
	{
        //计算当前C的值-> 用t来表示A0,B0,t的和C0
		if(i<A.size()) t += A[i];
		if(i<B.size()) t += B[i];
        //当前位
		C.push_back(t%10);
        //t>=10进位 t<=10为0
		t/=10;
	} 
    //最高位是否需要进位
	if(t) C.push_back(1);
	return C;
}
int main()
{
	string a,b;//字符串读入
	vector<int> A,B;
	cin >> a >> b;//a="123456"                                  //逆序遍历字母转数字
	for(int i = a.size()-1;i >= 0;i--) A.push_back(a[i] - '0'); // A= [6,5,4,3,2,1] 把字符串A的每一位拿出来放在vector数组中
	for(int i = b.size()-1;i >= 0;i--) B.push_back(b[i] - '0');
	auto C = add(A,B);
	for(int i = C.size()-1;i >= 0;i--) printf("%d",C[i]);       //逆序输出-> 先输出最高位,再输出次高位
}

高精度减法

??? 1????? 2????? 3
?-????????? 8????? 9
?——————
??????????? 3????? 4

???? A3????? A2????? A1????? A0 ????
?-???????????? B2????? B1????? B0
?———————————

如果 A 数组表示的数 ≥ B 数组表示的数，A - B

如果 A ＜ B，-（B - A）
Ai - Bi - t (借位，t == 0：没有借位，t == 1：有借位) ≥ 0，直接减 Ai - Bi - t

Ai - Bi - t (借位) ＜0，Ai - Bi + 10 - t

借位指的是借给下一位

两个大整数相减，如果存在负数，可以转换为 | A | - | B | 或者 | A | + | B | 的情况

用 (t +10) % 10 替换两种情况：

① t ≥ 0，t

② t < 0，t + 10

#include<iostream>
#include<cstdio> 
#include<vector>
#include<algorithm>
using namespace std;

//判断是否A≥B
bool  cmp(vector<int> &A, vector<int> &B) 
{
	//先判断两个数的位数-> 位数不同,如果A的位数大则A>B 
	if(A.size()!= B.size()) return A.size() > B.size();
	//位数相同比较两个数的大小-> 从高位开始比较,高位相同,比较次高位,直到找到一位不相同为止,所有位相同则A == B 
	//逆序存储-> 高位在最后一位,找到第一位不相等的,如果A比较大则A>B 
	for(int i = A.size() - 1;i >= 0;i--)
	if(A[i] != B[i])
		return A[i] > B[i];
    //所有位数的数都相等 A == B
	return true;
}
 
//C = A - B 
vector<int> sub(vector<int> &A, vector<int> &B)
{
    //存储结果
	vector<int> C;
	//从个位开始
    //已经保证A ≥ B
	for(int i = 0,t = 0;i < A.size();i++)
	{
        //计算当前位的值 t = A[i] - B[i] - t 
 		t = A[i] - t;
        //判断B是否存在-> B可能没有这一位,没有就是0,B的位数比A的位数少
		if(i<B.size()) t -= B[i];
        //当前位
		C.push_back((t+10)%10);
        //判断是否需要借位
		if(t < 0) t = 1;
		else t = 0;//不需要借位
	}
	//123 - 120 == 003 如果直接返回:A有多少位C就有多少位,需要去掉前导0 
	//>1如果123 - 123 == 0 如果结果只有一位是0,需要保留一位 其他情况: 如果最后一位等于0,把最后一位干掉 
	while(C.size()>1 && C.back() == 0) C.pop_back();  
	return C;
}
int main()
{
	string a,b;//字符串读入
	vector<int> A,B;
	cin >> a >> b;//a="123456" 把字符串A的每一位拿出来放在vector数组中,逆序遍历,字母转数字 
	for(int i = a.size()-1;i >= 0;i--) A.push_back(a[i] - '0'); // A= [6,5,4,3,2,1] 
	for(int i = b.size()-1;i >= 0;i--) B.push_back(b[i] - '0');
    //判断哪个大整数更大
    if(cmp(A,B))
    {
        auto C = sub(A,B);
        for(int i = C.size()-1;i >= 0;i--) printf("%d",C[i]);   //逆序输出-> 先输出最高位,再输出次高位
    }
	else
	{
		auto C = sub(B,A);
		printf("-");
		for(int i = C.size()-1;i >= 0;i--) printf("%d",C[i]);   //逆序输出-> 先输出最高位,再输出次高位
	}
	return 0; 
}