DDD学习笔记

# 排序算法概述
## 排序
将一组数据按指定方式进行排列的过程叫做排序，常见的排序算法有八种



![排序算法种类](https://kid-cos-1310921471.cos.ap-shanghai.myqcloud.com/blog/46b25ebc51d3b0eb82f4006169b24679.1.webp)

## 排序算法的对比情况：

![2.png](https://kid-cos-1310921471.cos.ap-shanghai.myqcloud.com/blog/0a9a25b0250c87cb997e4ffcceddff12.2.webp)

# 八大排序（原理+代码）


## 1.冒泡排序
原理：最经典的排序算法，每次比较相邻两数大小，如果为逆序，则交换这两个数，flag用来检查本次是否交换了，如果没有，证明已经排好序，可以直接退出。

代码：
```cpp
void BubbleSort(vector<int> &a){		
	for(int i=a.size()-1;i>=0;i--){
		int flag=0;
		for(int j=0;j<i;j++){
			if(a[j]>a[j+1]){
				swap(&a[j],&a[j+1]);
				flag++;
			}
		}
		if(!flag) return;
	}
}
```
## 2.选择排序
原理：第一次从a[0]-a[n-1]选出一个最小值与a[0]交换，第二次从a[1]-a[n-1]选出最小值与a[1]交换，以此类推。

代码：
```cpp
void SelectSort(vector<int> &a){		
	for(int i=0;i<(int)a.size()-1;i++){
		int value=1e9+7,index=i;
		for(int j=i;j<(int)a.size();j++){
			if(a[j]<value){
				index=j;
				value=a[j];
			}
		}
		swap(&a[i],&a[index]);
	}
}
```
## 3.插入排序
原理：将n个元素看作一个有序表与一个无序表，开始时有序表只有一个元素，排序时每次将无序表中的一个元素插入到有序表中的适当位置，使之成为一个新的有序表。

代码：
```cpp
void InsertSort(vector<int> &a){		
	for(int i=1;i<(int)a.size();i++){
		int index=i-1,value=a[i];
		while(a[index]>value&&index>=0){
			a[index+1]=a[index];
			index--;
		}
		a[index+1]=value;
	}
}
```
## 4.希尔排序
原理：把数组按一定的增量分组，每组进行插入排序，随着增量减少，每组关键词越来越多，当增量减少为1的时候，整个数组恰好被分为一组，此时排序终止。
希尔排序是一种插入排序经过改进后的更高效的排序，也是一种插入排序，也称为缩小增量排序。

代码：
```cpp
void ShellSort(vector<int> &a){			
	for(int gap=a.size()/2;gap>0;gap/=2){
		for(int i=gap;i<(int)a.size();i++){
			int j=i,t=a[i];
			if(a[j]<a[j-gap]){
				while(j-gap>=0&&t<a[j-gap]){
					a[j]=a[j-gap];
					j-=gap;
				}
				a[j]=t;
			}
		}
	}
}
```
## 5.快速排序
原理：是使用最广泛的排序，对冒泡排序的一种改进，通过一趟排序将数组分割成两部分，其中一部分所有数据都比另一部分小，再对这两部分分别使用快速排序（可用递归），以此达到所有数据有序。

代码：
```cpp
void QuickSort(vector<int> &a,int l,int r){
	if(l>=r) return;
	int i=l,j=r;
	while(i!=j){
		while(a[j]>a[l]&&j>=i) j--;
		while(a[i]<a[l]&&i<=j) i++;
		swap(&a[i],&a[j]);
	}
	swap(&a[l],&a[i]);
	QuickSort(a,l,i-1);
	QuickSort(a,i+1,r);
}
```
## 6.归并排序
原理：利用归并思想，采用分治策略，递归拆分子序列，然后将两个有序的子序列合并成一个有序的子序列，最终合并所有的子序列得到一个有序序列。

代码：
```cpp
void MergeSort(vector<int> &a,int l,int r,int *tmp){
	if(l>=r) return;
	int mid=(l+r)/2;
	MergeSort(a,l,mid,tmp);
	MergeSort(a,mid+1,r,tmp);
	int i=l,j=mid+1,t=0;
	while(i<=mid&&j<=r){
		if(a[i]<a[j]){
			tmp[t++]=a[i++];
		}
		else{
			tmp[t++]=a[j++];
		}
	}
	while(i<=mid){
		tmp[t++]=a[i++];
	}
	while(j<=r){
		tmp[t++]=a[j++];
	}
	t=0;
	int tl=l;
	while(tl<=r){
		a[tl++]=tmp[t++];
	}
}
```
## 7.基数排序
原理：基数排序是桶排序的扩展，属于分配式排序。将整数按位切割成不同数字，然后按每个位数分别比较。

代码：
```cpp
void RadixSort(vector<int> &a){
	vector<int> bucket[10];
	for(int i=10;;i*=10){
		for(int j=0;j<(int)a.size();j++){
			bucket[a[j]*10/i%10].push_back(a[j]);
		}
		if(a.size()==bucket[0].size()) return;
		int t=0;
		for(int j=0;j<10;j++){
			for(int k=0;k<(int)bucket[j].size();k++){
				a[t++]=bucket[j][k];
			}
			bucket[j].clear();
		}
	}
}
```

## 8.堆排序
原理：
1）将待排序的n个数据构造成一个大顶堆
2）将根节点与末尾元素互换
3）将剩余n-1个元素重新构造一个大顶堆
4）反复执行得到有序的序列

代码：
```cpp
void Sift(vector<int> &a,int head,int tail) {
	int dad=head,son=dad*2+1;
	while(son<=tail) {
		if(son+1<=tail&&a[son]<a[son+1])
			son++;
		if(a[dad]>a[son])
			return;
		else {
			swap(a[dad],a[son]);
			dad=son;
			son=dad*2+1;
		}
	}
}

void HeapSort(vector<int> &a) {
	for(int i=a.size()/2-1; i>=0; i--) {
		Sift(a,i,a.size()-1);
	}
	for(int i=a.size()-1; i>0; i--) {
		swap(a[i],a[0]);
		Sift(a,0,i-1);
	}
}
```

排序算法概述

大一新生，刚看题目觉得不难，试图暴力枚举，结果失败，遂放弃，打完后才反应过来是搜索，于是又重写了一遍，记于此提醒自己。



分析题目，这就是个3种不同的小球不重复排列组合的题，于是我简化了一下，让k为1，d为2，a为3开始排列组合，每组合出一种结果判断是否25层，最后输出所有符合的个数，简简单单。

最开始套了个模板，结果超时了一点

```cpp
#include<iostream>
using namespace std;

#define kk 5
#define dd -10
#define aa 2
int b[21]= {0},sum=0,book[4]= {0},sumn=0; //初始化数据数组，标记数组，总层数，满足的情况总数，一定是全局变量，因为每层递归需要用上一次的结果
int k,d,a,n;

//算法核心，一个简单的深度搜索
void dfs(int s) {
	if(s==n+1) {        //如果到结尾了，判断层数是否等于25
		sum=0;
		for(int i=1;i<=n;i++){
			if(b[i]==1) sum+=kk;    //计算层数
			if(b[i]==2) sum+=dd;
			if(b[i]==3) sum+=aa;
			if(sum<0) sum=0;           //低于0层也是0层
			if(sum>25) sum=25;        //高于25层也是25层
		}
		if(sum==25) sumn++;    //如果层数满足，总数加一
		return;
	}
    
    //每一位开始递归
	for(int j=1; j<=3; j++) {
		if(book[j]) {        //如果还有此种数据就把它扔一个进数组去
			b[s]=j;
			book[j]--;        //该种数据个数减一
			dfs(s+1);           //递归判断下一位
			book[j]++;        //再倒着把这种数据捡回来
		}
	}
	return;
}

//主函数
int main() {
	cin>>k>>d>>a;
	n=k+d+a;
	book[1]=k;    //初始化标记数组，存储k,d,a的个数
	book[2]=d;
	book[3]=a;
	dfs(1);        //从第一位开始递归
	cout<<sumn;
	return 0;
}
```

我一看，这个判断层数没必要等组合出来再从头算啊，如果前面的都一样，最后两位不一样，那岂不是浪费功夫，于是我就把判断也加到了递归里

```cpp
#include<iostream>
using namespace std;

int b[21]= {0},sum=0,book[4]= {0},sumn=0,bj[4]= {0,5,-10,2};
int k,d,a,n;

//简化过程
void dfs(int s) {
	int t;							//一个中间变量t，存储新加一个数据之前的总层数，不能是全局变量，只让它在本层递归起作用
	if(s==n+1) {					//同样的，到了总长度时就判断层数
		if(sum==25) sumn++;
		return;
	}
	for(int j=1; j<=3; j++) {
		if(book[j]) {
			b[s]=j;
			book[j]--;
			t=sum;					//存储之前的层数
			sum+=bj[j];				//新的数据改变层数
			if(sum<0) sum=0;		//一样的让它处于0到25
			if(sum>25) sum=25;
			dfs(s+1);				//递归下一位
			book[j]++;				//还回来一个数据
			sum=t;					//总层数也还原
		}
	}
	return;
}

//主函数
int main() {
	cin>>k>>d>>a;
	n=k+d+a;
	book[1]=k;
	book[2]=d;
	book[3]=a;
	dfs(1);
	cout<<sumn;
	return 0;
}
```

果然，快了一倍还多，可以打出GG了。

2021.12.11吉首大学新生杯Problem C梅贾的窃魂卷

[原题地址](https://www.luogu.com.cn/problem/P1706)

法一：dfs，可直接搜索，数据规模小或需要输出具体排列时使用



```cpp
#include<bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = (int)(a); i <= (int)(b); ++i)
#define rrep(i, a, b) for(int i = (int)(a); i < (int)(b); ++i)
#define lep(i, a, b) for(int i = (int)(a); i >= (int)(b); i--)
#define UPS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endn puts("")

typedef long long LL;
typedef unsigned long long ULL;
const int INF = 0x3f3f3f3f, MOD = 1e9 + 7;
const double EPS = 1e-7, PI = acos(-1);
/*=======================================*/
int book[10]= {0},s=0;
int n,arr[10]= {0};

void dfs(){
	if(s==n){
		rrep(i,0,n){
			printf("%5d",arr[i]);
		}
		endn;
	}
	rep(i,1,n){
		if(!book[i]){
			book[i]++;
			arr[s++]=i;
			dfs();
			s--;
			book[i]--;
		}
	}
}

int main() {
	UPS;
	cin>>n;
	dfs();
	return 0;
}

```

法二：使用c++自带的库函数next_permutation()，此库函数会将一段数组变为它的下一个全排列，只需统计次数，然后调用即可。

```cpp
#include<bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = (int)(a); i <= (int)(b); ++i)
#define rrep(i, a, b) for(int i = (int)(a); i < (int)(b); ++i)
#define lep(i, a, b) for(int i = (int)(a); i >= (int)(b); i--)
#define UPS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endn puts("")

typedef long long LL;
typedef unsigned long long ULL;
const int INF = 0x3f3f3f3f, MOD = 1e9 + 7;
const double EPS = 1e-7, PI = acos(-1);
/*=======================================*/
int sum=1;
int n,arr[10]= {0};

int main() {
	UPS;
	cin>>n;
	rrep(i,0,n) arr[i]=n-i,sum*=arr[i];
	for(int i=1;i<=sum;i++){
		next_permutation(arr,arr+n);
		rrep(i,0,n) {
			printf("%5d",arr[i]);
		}
		endn;
	}
	return 0;
}
```

全排列问题（洛谷P1706）

八皇后问题（英文：Eight queens），是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。



问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

原理：用递归来模拟每一行，用循环来模拟一行中的每一格，检查当前格能否满足条件，如果一直到第八行结束都满足，则更新一种解法。

原始解法：由于数量级小，可以用二维数组来表示坐标，当模拟到某一格时，检查在对角线或者同列有没有其他已经被标记过的点，如果没有，就进入下一次递归，也就是模拟下一行，直到模拟结束，cnt就是所求的结果。

优化：可以用一维数组来代替二维数组，因为行号是顺序的，所以可以用数组下标来表示行，数组元素表示这一行的第几列加入这种解法。check()函数用来检查有没有和之前的点同列或者同对角线，比二维数组的方法更加简单，时间和空间也都有所优化。


解法：

```cpp
#include<bits/stdc++.h>
#include<windows.h>
using namespace std;

#define rep(i, a, b) for(int i = (int)(a); i <= (int)(b); ++i)
#define rrep(i, a, b) for(int i = (int)(a); i < (int)(b); ++i)
#define lep(i, a, b) for(int i = (int)(a); i >= (int)(b); i--)
#define UPS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

typedef long long LL;
typedef unsigned long long ULL;
const int INF = 0x3f3f3f3f, MOD = 1e9 + 7;
const double EPS = 1e-7, PI = acos(-1);
/*=======================================*/
short arr[13]={0},s=1,m=8;
LL sum=0;
int cnt=0;

int check(int n){
	
	rrep(i,1,s){
		sum++;
		if(arr[i]==n) return 0;
		if((int)fabs(i-s)==(int)fabs(arr[i]-n)) return 0;
	}
	return 1;
}

void dfs(){
	if(s==m+1){
		cnt++;
		return;
	}
	rep(i,1,m){
//		if(arr[s][i]==0){				//此处为原始解法
//			v[s]=i;
//			rep(j,1,8){
//				arr[s][j]++;
//				arr[j][i]++;
//				int fs=(int)fabs(s-j);
//				if(i-fs>0) arr[j][i-fs]++;
//				if(i+fs<=8) arr[j][i+fs]++;
//			}
//			arr[s][i]-=3;
//			s++;
//			dfs();
//			s--;
//			arr[s][i]+=3;
//			rep(j,1,8){
//				arr[s][j]--;
//				arr[j][i]--;
//				int fs=(int)fabs(s-j);
//				if(i-fs>0) arr[j][i-fs]--;
//				if(i+fs<=8) arr[j][i+fs]--;
//			}
//		}
		if(check(i)){
			arr[s++]=i;
			dfs();
			s--;
		}
	}
}

int main(){
	UPS

	LARGE_INTEGER t1,t2,tc;
	QueryPerformanceFrequency(&tc);
	QueryPerformanceCounter(&t1);

	dfs();
	cout<<cnt<<endl;
	cout<<sum<<endl;
	
	QueryPerformanceCounter(&t2);
	double time=(double)(t2.QuadPart-t1.QuadPart)/(double)tc.QuadPart;
	cout<<"time = "<<time*1000<<"ms"<<endl;
	
	return 0;
}
```

DDD 学习笔记

排序算法概述

排序