快速排序

参照《算法导论》

快排采用分治思想：

分解
数组A[p…r]被分为两个子数组A[p…q-1]和A[q+1…r]，使得A[p…q-1]中的每一个元素都小于等于A[q],A[q+1…r]中的每一个元素都大于等于A[q]
解决
通过递归，对子数组A[p…q-1]和A[q+1…r]进行排序
合并
子数组都是原址排序，所以不需要合并操作：A[p…r]已经有序

QUICKSORT(A,p,r)
if p<r
	q=PARTITION(A,p,r)
	QUICKSORT(A,p,q-1)
	QUICKSORT(A,q+1,r)

PARTITION的实现

PARTITION(A,p,r)
x=A[r]	//始终将最右边的元素作为主元，围绕它来划分子数组
i=p-1	//i标记左界
for j=p to r-1	//j标记右界
	if(A[j]<=x)
		i=i+1
		exchange A[i] with A[j]	//这样保证i、j之间（i右侧至j左侧）的数始终大于x，便于维护子数组性质
exchange A[i+1] with A[r]	//此时最中间的数为主元
return i+1	//找到了q的位置

代码实现

#include<bits/stdc++.h>
using namespace std;
void exchange(int *a,int *b){
	int tmp;
	tmp=*a;
	*a=*b;
	*b=tmp;
}
int PARTITION(int n[],int l,int r){
		int i=l-1;
		for(int j=l;j<=r-1;j++){
			if(n[j]<=n[r]){
				i++;
				exchange(&n[j],&n[i]);
			}
		}
		exchange(&n[i+1],&n[r]);
		return i+1;
}
void QUICKSORT(int n[],int l,int r){
	if(l<r){
		int m=PARTITION(n,l,r);
		QUICKSORT(n,l,m-1);
		QUICKSORT(n,m+1,r);
	}
}
int main(){
	freopen("input.txt","r",stdin);
	int n[10086],f=1;
	while(~scanf("%d",&n[f]))
		f++;
	QUICKSORT(n,1,f-1);
	while((f--)&&(f>=1))
		cout<<n[f]<<'\0';
	return 0;
}

类

访问属性

public 类外可访问、修改
private 不能类外访问、修改

例

class pair{
	public :
		int can;
	private :
		int cannot;
};
int main(){
	pair a;
	a.can=2;	//可以（can是public）
	a.cannot=2;	//不行（cannot是private）
	return 0;
}

成员函数

通过使用类里面定义的函数，可以修改private成员

#include<bits/stdc++.h>
using namespace std;
class ex{
	private:
		int n=1;
	public:
		int gtn(void){
			return n;
		}
		void plus(int a,int b){
			n=a+b;
		}
}num;
int main(){
	cout<<num.gtn()<<endl;
	num.plus(2,1);
	cout<<num.gtn();
	return 0;
}

输出结果

1
3

友元函数

使类外函数也能访问、修改private成员
使用关键字friend

#include<bits/stdc++.h>
using namespace std;
class exm{
	public :
		friend int getn(void);
	private :
		int n=4;
}nu;
int getn(void){
	return nu.n;
}
int main(){
	cout<<getn();
	return 0;
}

输出结果

重载运算符

operator运算符名

如重载+

#include<bits/stdc++.h>
using namespace std;
class cls{
	private :
		int tot;
	public :
		friend int operator+(cls a,cls b);
		int getnumb(void){
			return tot;
		}
		void input(int n){
			tot=n;
		}
}numb_1,numb_2,numb_3;
int operator+(cls a,cls b){
	return a.getnumb()+b.getnumb();
}
int main(){
	numb_2.input(20);
	numb_3.input(30);
	numb_1.input(numb_2+numb_3);
	cout<<numb_1.getnumb();
	return 0;
}

输出结果

高精度计算

原理：将数字以字符串形式读入，逢10进1（模拟竖式计算）。数字0 ~ 9对应的ASCII值为48 ~ 57，计算时将该位字符 -‘0’ 即 -48 即可将字符转化为数字进行计算。

#include<bits/stdc++.h>
using namespace std;
int len1,len2;
class gj{
	private:
		int i,x;
	public:
		int n[10086];
		void cal_1(gj a,gj b){
			i=0,x=0;
    		while( i<=len1 || i<=len2 ){
        		n[i]=a.n[i]+b.n[i]+x;
        		x=n[i]/10;
        		n[i]%=10;
        		i++;
    		}
    		n[i]=x;
    		while(n[i]==0 && i!=0) i--;
		}
		void output(void){
			for (int j=i;j>=0;j--){
        		printf("%d",n[j]);
    		}
    		printf("\n");
		}
}n1,n2,as;
string js1,js2;
int main(){
	cin>>js1>>js2;
	len1=js1.size(),len2=js2.size();
	for (int i=len1-1,j=0;i>=0;i--,j++)
    {
        n1.n[j]=js1[i]-'0';
    }
    for (int i=len2-1,j=0;i>=0;i--,j++)
    {
        n2.n[j]=js2[i]-'0';
    }
    as.cal_1(n1,n2);
    as.output();
	return 0;
}