|
1.九种排序算法(八种排序＋二叉排序树的中序遍历)
(1)冒泡排序,最简单的一种
//冒泡排序,复杂度为n的二次方--------------------------------------------------------
void bubble(int arr[], int length) {
for (int i = length; i >= 1; i--) {
for (int j = 1; j < i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, arr[j], arr[j + 1]);
}
}
}
}
(2)简单排序,思想是把队列中最小的元素放在最前面,然后从下一个元素开始到末尾继续进行这个操作
//简单排序--------------------------------------------------------------------------
void simpleSort(int arr[], int length) {
int min = 0;
for (int i = 1; i <= length; i++) {
min = i;
for (int j = i; j <= length; j++) {
if (arr[j] < arr[min])min = j;
}
swap(arr, i, min);
}
}
(3)插入排序,思想是一旦前面的数字小于当前数字的数值,就开始向后赋值,直到找到合适的位置进行插入
例如? ? 1?3 4 5 2-------先把2储存为temp;
? ? ? ? ? ?1 3 4 5 5------1 3 4 4 5-------1 3 3 4 5,这时候1小于temp,所以变成了1 [2] 3 4 5,排序完成
//插入排序
//如果前面的比自己大那就把数字换成前面的
//然后依次往下找,直到前面没有比自己大的了,而且此时自己后面的已经附上了自己的数值--
//这个位置就可以进行插入了
void insertSort(int arr[],int length) {
for (int i = 2; i <= length; i++) {
if (arr[i] < arr[i - 1]) {
int k; int temp = arr[i];
for (k = i-1; k >= 1 && temp < arr[k]; k--) {
arr[k+1] = arr[k];
}
arr[k+1] = temp;
}
}
}
(4)希尔排序,思想就是再逐个递减的increment的基础上,再次使用插入排序
//希尔排序(跳跃版本的插入排序)--------------------------------------------------
void shell(int arr[], int length) {
int increment = length;
do {
increment = increment / 3 + 1;
for (int i = increment+1; i <= length; i++) {
if (arr[i - increment] > arr[i]) {
int k; int temp = arr[i];
for (k = i-increment; k >= 1 && temp < arr[k]; k-= increment) {
arr[k+increment] = arr[k];
}
arr[k + increment] = temp;
}
}
} while (increment > 1);
}
(5)堆排序,某种意义上来说是树结构上的插入排序
//堆排序-------可以理解为完全二叉树中的希尔排序---------------------------------
//堆排序的大致原理为:
//根节点的两个孩子(也可能有一个,需要具体判断)
void bigstock(int arr[],int start,int end) {//这个方法的使用前提是,基本成型,或者从下网上构建
int temp = arr[start];
for (int i = start*2; i <= end; i *= 2) {
if (i<end && arr[i] < arr[i + 1]) i++;
if (temp > arr[i]) break;
arr[start] = arr[i];
start = i;
}
arr[start] = temp;
}
void stockSort(int arr[], int length) {
for (int i = length / 2; i > 0; i--) {//这里出现过问题,i最终是需要到1的
bigstock(arr, i, length);
}
for (int i = length; i > 1; i--) {//这个1 2都行
swap(arr, 1, i);
bigstock(arr, 1, i-1);
}
}
(6)计数排序,只能对纯数字生效,储存下来每个数字的出现次数,然后遍历原本的数组,按出现次数安插到新数组的位置
//计数排序(仅限于纯数字的排序,这个其实更适合第0位开头的数组)---------------------------------
void countSort(int arr[], int length, int m) {
int equal[10] = {0,0,0,0,0,0,0,0,0,0};
int less[10] = {0,0,0,0,0,0,0,0,0,0};
for (int i = 1; i <= length; i++)
equal[arr[i]]++;
for (int i = 1; i <= m; i++)
less[i] = less[i - 1] + equal[i - 1];
int point = 0;
int Brr[50];
for (int i = 0; i <= length; i++)
Brr[i] = arr[i];
for (int i = 0; i <= length; i++) {
arr[1 + less[Brr[i]]++] = Brr[i];
}
}
(7)快速排序:原理和前序遍历比较像
//快速排序,不被大佬建议使用的一种排序,原理是前序遍历----------------------------------------
int Quick(int arr[], int p, int q) {
int point = 0;
for (int i = p; i < q - 1; i++) {
if (arr[i] <= arr[q]) {
swap(arr, i, point);
point++;
}
}
swap(arr, q, point);
return point;
}
void QuickSort(int arr[], int p, int q) {
if (q > p) {
int r = Quick(arr, p, q);
QuickSort(arr, p, r-1);
QuickSort(arr, r+1, q);
}
}
(8)归并排序:原理和后序遍历很像
//归并排序,使用递归中的后序遍历,相对最稳定---------------------
void Merge(int arr[], int p,int r, int q) {
int B[50]; int C[50];
int pointB = 0; int pointC = 0;
for (int i = p; i <= r; i++) {
B[i - p] = arr[i];
}
for (int i = r+1; i <= q; i++) {
C[i - r - 1] = arr[i];
}
B[r-p+1] = 100; C[q-r] = 100;
for (int i = p; i <= q; i++) {
if (B[pointB] >= C[pointC]) {
arr[i] = C[pointC++];
}
else{
arr[i] = B[pointB++];
}
}
}
void MergeSort(int arr, int p, int q) {
if (q > p) {
int r = (p + q) / 2;
MergeSort(arr,p,r);
MergeSort(arr,r+1,q);
}
}
(9)二叉排序树:利用中序遍历可以读取树里的内容,详见讲解树的部分.
//再拓展出一种二叉树排序
class Node {
public:
int num;
Node* left=NULL;
Node* right=NULL;
};
void createtree(Node*& root, int num) {
if (root == NULL) {
root = new Node;
root->num = num;
}
else {
if(num < root->num)
createtree(root->left, num);
if (num > root->num)
createtree(root->right, num);
}
}
2.关于图有关的一部分算法
(1)关于图的储存方式,大体上可以分为三种 接邻矩阵 接邻表 边集数组
接邻矩阵:常用的两种是接邻表和权重表,接邻表没有权重,两个结点相邻时赋值1,不相邻的时候赋值为0(除非自带一共环,否则自己到自己也是0).? 而权重表是相邻则记录边的权重,不相邻记录为max,自己到自己记录为0.
下面分别为权重表和接邻表的创建储存方式
int arr[7][7];
for (int i = 0; i <= 6; i++) {
for (int j = 0; j <= 6; j++) {
if (i == j)
arr[i][j] = 0;
else
arr[i][j] = 100;
}
}
int edgeNum, x, y, weight; cout << "下面请输入边的数目" << endl; cin >> edgeNum;
for (int i = 1; i <= edgeNum; i++) { cin >> x >> y>>weight; arr[x][y] = weight; arr[y][x] = weight; }
//权重无向图创建完成
int arr[7][7];
for (int i = 0; i <= 6; i++) {
for (int j = 0; j <= 6; j++) {
arr[i][j] = 0;
}
}
int edgeNum, x, y; cout << "下面请输入边的数目" << endl; cin >> edgeNum;
for (int i = 1; i <= edgeNum; i++) { cin >> x >> y ; arr[x][y] = 1; arr[y][x] = 1; }
接邻表:分为普通接邻表和十字接邻表,普通接邻表的结构如下
创建一共头节点类型的数组,头节点里面可以储存相关的信息,然后每个头节点都自带一个指针指向链表的第一个.这样访问和记录数据都方便很多.
每个结点需要的数据是adj(序号)? weight(权重) next(指针域)
十字链表自带一个前驱的链表,本质上差不太多
class Node {
public:
int num;
int weight;
Node* next;
Node(int a) { num = a; };
};
class headNode {
public:
int length = 0;
Node* point=NULL;
int in, out = 0;
};
class graph {
public:
headNode arr[10];
int NodeNum, EdgeNum = 0;
};
void createGraph(graph& Graph) {
int edge, point,start,end,weight;
cout << "请输入边数 和 点数" << endl;
cin >> edge >> point;
Graph.EdgeNum = edge;
Graph.NodeNum = point;
for (int i = 0; i < point; i++) {
Graph.arr[i] = headNode();
}
for (int i = 1; i <= edge; i++) {
cin >> start >> end >> weight;
Graph.arr[start].out++;//出度+1
Graph.arr[end].in++;//入度+1
Node* temp = new Node(end);
temp->weight = weight;//赋予权重
temp->next = Graph.arr[start].point;
Graph.arr[start].point = temp;//头插法插入
}
}
//图结构已经储存完毕;
边集数组:边集数组是专门用于边这样子,储存方式如下
起点,终点,权重三个方向的数值
kruNode arr[10] = {
kruNode(0,1,1),kruNode(2,4,1),kruNode(1,5,1),kruNode(4,6,1),kruNode(5,6,1),
kruNode(0,2,2),kruNode(1,3,2),kruNode(3,4,2),kruNode(3,6,3),kruNode(1,2,3)
};
(2)图的遍历方法,分为两种
深度遍历搜索DFS:原理类似于前序遍历,每次读取到一个没有访问过的点,就先打上标记进行输出,然后看这个点的子代进行遍历(递归操作)
int visited[50];
void DFSserver(int arr[7][7],int i) {
if (visited[i] != 1) {
cout << i << endl; visited[i] = 1;
for (int j = 0; j <= 6; j++) {
int temp = arr[i][j];
DFSserver(arr, temp);
}
}
}
void DFS() {
int arr[7][7];
for (int i = 0; i <= 6; i++) {
for (int j = 0; j <= 6; j++) {
arr[i][j] = 0;
}
}
int edgeNum, x, y; cout << "下面请输入边的数目" << endl; cin >> edgeNum;
for (int i = 1; i <= edgeNum; i++) { cin >> x >> y ; arr[x][y] = 1; arr[y][x] = 1; }
for (int i = 0; i <= 6; i++)
visited[i] = 0;
for (int i = 0; i <= 6; i++)
DFSserver(arr, i);
}
BFS广度遍历搜索
原理据说是类似层序遍历,不过层序遍历我还没写过,每次读取一个点,如果这个点没有走过,就把这个点存入队列中,并标记走过.然后每次弹出一个点,输出的同时,把这个点没有经过的点也存入队列中
为了提升运算速度和防止特殊情况(比如一个图里有两个相互独立的连通分量),使用遍历操作,让每个点都充当一次队列中的第一点(最外面加的那个for循环和if判断)
//深度遍历的邻接表
//原理是依托队列进行层序遍历
void BFS() {
int arr[7][7];
for (int i = 0; i <= 6; i++) {
for (int j = 0; j <= 6; j++) {
arr[i][j] = 0;
}
}
int edgeNum, x, y; cout << "下面请输入边的数目" << endl; cin >> edgeNum;
for (int i = 1; i <= edgeNum; i++) { cin >> x >> y; arr[x][y] = 1; arr[y][x] = 1; }
for (int i = 0; i <= 6; i++)
visited[i] = 0;
//上面是对于边和visited数组进行赋值
queue<int> Queue;
for (int n = 0; n <= 6; n++) {//加或者不加..顺序没有区别
if (visited[n] != 1) { //大概是为了节约一部分运算吧.....
Queue.push(n); visited[n] = 1;
while (!Queue.empty()) {
int temp = Queue.front(); Queue.pop(); cout << temp << endl;
for (int i = 0; i <= 6; i++) {
if (visited[i] != 1 && arr[temp][i] == 0) {
Queue.push(i); visited[i] = 1;
}
}
}
}
}
}
(3)图的三种最短路径算法
1.迪杰斯特拉算法,原理是利用接邻矩阵进行存储,选取一个dis数值最小而且没有经过的点作为中转点进行松弛操作(dis为起点到其他点的最短路径,而且使用另外一个数组来记录某个点是不是已经经过了)
松弛操作的原理:A到B点的路途>A到中转点+中转点到B,那么A到B的距离就更新为这个
void dijiesitela() {
//原理,每次选取入度最小的一个点以这个点作为中转点遍历其他的点
int arr[7][7];
for (int i = 0; i <= 6; i++) {
for (int j = 0; j <= 6; j++) {
if (i == j)
arr[i][j] = 0;
else
arr[i][j] = 100;
}
}
int edgeNum, x, y, weight; cout << "下面请输入边的数目" << endl; cin >> edgeNum;
for (int i = 1; i <= edgeNum; i++) { cin >> x >> y >> weight; arr[x][y] = weight; arr[y][x] = weight; }
int distant[7] = { 0,1,2,100,100,100,100 };//一共七个点
int visited[7] = { 0,1,1,1,1,1,1 };
for (int i = 1; i <= 6; i++) {
int k = 0; int min = 100;
for (int x = 0; x < 7; x++) {
if (visited[x] != 0 && min > distant[x]) {
min = distant[x]; k = x;
}
}
visited[k] = 0;//代表这个点已经经过访问
for (int x = 0; x < 7; x++) {
if (distant[x] > distant[k] + arr[x][k]) {
distant[x] = distant[k] + arr[x][k];
}
}
}
for (int x = 0; x < 7; x++) {
cout << distant[x] << endl;
}
}
2.贝尔曼福特算法
原理:利用边集数组进行储存,原理依然是每个点作为中转点松弛操作,不过这要重复n-1次进行矫正
//贝尔曼福特用的是边集数组进行处理
void bellman() {
kruNode arr[10] = {
kruNode(0,1,1),kruNode(2,4,1),kruNode(1,5,1),kruNode(4,6,1),kruNode(5,6,1),
kruNode(0,2,2),kruNode(1,3,2),kruNode(3,4,2),kruNode(3,6,3),kruNode(1,2,3)
};
int dis[7] = { 0,100,100,100,100,100,100 };
for (int i = 1; i <= 6; i++) {
for (int j = 0; j <= 9; j++) {
if (dis[arr[j].end] > dis[arr[j].start] + arr[j].weight) {
dis[arr[j].end] = dis[arr[j].start] + arr[j].weight;
}
}
}
for (int x = 0; x < 7; x++) {
cout << dis[x] << endl;
}
}
3.弗洛伊德算法,纯暴力破解了就是
使用接邻矩阵(由于没有筛选机制,所以同样是重复n-1次数)
void floyd() {
int arr[7][7];
for (int i = 0; i <= 6; i++) {
for (int j = 0; j <= 6; j++) {
if (i == j)
arr[i][j] = 0;
else
arr[i][j] = 100;
}
}
int edgeNum, x, y, weight; cout << "下面请输入边的数目" << endl; cin >> edgeNum;
for (int i = 1; i <= edgeNum; i++) { cin >> x >> y >> weight; arr[x][y] = weight; arr[y][x] = weight; }
int dis[7] = { 0,100,100,100,100,100,100 };
for (int i = 1; i <= 6; i++) {
for (int x = 0; x <= 6; x++) {
for (int y= 0; y <= 6; y++) {
if (dis[y] > dis[x] + arr[x][y]) {
dis[y] = dis[x] + arr[x][y];
}
}
}
}
for (int x = 0; x < 7; x++) {
cout << dis[x] << endl;
}
}
(4)图的两种最小生成树方法
prim算法,原理是集团化,其中利用visited数组来判断,如果为0则代表该点已经在集合内部
?同时准备group数组,来记录集团到各个点的距离
准备adjvex数组,来记录每个点的上一个是什么
每次(这样重复六次)寻找距离最近的点k存入集团中(标记为0),然后输出adjvex[k]和k
再然后遍历其他没有经过的点,如果集团到该点的距离大于k点到该点的距离,则group数组就进行调整,同时把该点的上一级记录为k
void prim() {
int arr[7][7];
for (int i = 0; i <= 6; i++) {
for (int j = 0; j <= 6; j++) {
if (i == j)
arr[i][j] = 0;
else
arr[i][j] = 100;
}
}
int edgeNum, x, y, weight; cout << "下面请输入边的数目" << endl; cin >> edgeNum;
for (int i = 1; i <= edgeNum; i++) { cin >> x >> y>>weight; arr[x][y] = weight; arr[y][x] = weight; }
//权重无向图创建完成
//前面都是图的创建,这里才是算法的核心内容
int group[7] = { 0,1,2,100,100,100,100 };
int adjvex[7] = { 0,0,0,0,0,0,0 };
for (int i = 1; i <= 6; i++) {//重复n-1次数
int min = 100;
int newNode = 0;
for (int k = 0; k < 7; k++) {
if (group[k] != 0 && group[k] < min) {
min = group[k]; newNode = k;
}
}
//NodeNew为最小的边的终点,min为最小边的值
group[newNode] = 0;
cout << adjvex[newNode] << "-----" << newNode << endl;
for (int k = 0; k<7; k++) {
if (group[k] != 0&&group[k]>arr[newNode][k]) {
group[k]=arr[newNode][k];
adjvex[k] = newNode;
}
}
}
}
krusal算法;
prim算法是走一步看一部,krustal用空间换成时间,利用边集数组进行存储(数组按权重从低到高进行排列),然后遍历每条边的时候检验是不是构成环,如果没有构成环就输出,并且start和end的头节点关联一下
关于是否构成环的算法,就是判断两个点追根溯源,是不是同一个启示点.这里使用类似静态链表的数组,每个位置上存在自己上一位的地址.然后使用递归/循环的方法溯源 .
int sethead(int arr[],int num) {//寻找开头点
if (arr[num] == -1) {//判定,如果再上一个点是-1,那么就可知已经溯源到了极限了
return num;
}
else {
return sethead(arr, arr[num]);
}
}
void krustal() {
//使用边集数组来储存图的信息最好
kruNode arr[10] = {
kruNode(0,1,1),kruNode(2,4,1),kruNode(1,5,1),kruNode(4,6,1),kruNode(5,6,1),
kruNode(0,2,2),kruNode(1,3,2),kruNode(3,4,2),kruNode(3,6,3),kruNode(1,2,3)
};
int A, B;
int prev[10] = { -1,-1,-1,-1,-1,-1,-1,-1,-1,-1 };
for (int i = 0; i <= 9; i++) {
A = sethead(prev, arr[i].start);
B = sethead(prev, arr[i].end);
if (A != B) {
cout << arr[i].start << "-----" << arr[i].end << endl;
prev[B] = arr[i].start;
}
}
}
(5)图的关键路径算法
etv数组在拓扑排序的时候,按照拓扑正序进行存储
ltv数组按拓扑逆序进行处理
//图结构已经储存完毕;(graph为邻接表进行存储)
//关键路径算法
//受到学妹的启发,终于明白这个最短是什么意思了
//最短并非指的是从起点到终点的最短距离(事实上这个也能求,不过理论上不行)
//关键路径的时间加起来,其实是完成所有任务需要的最短时间(默认任务是可以并发完成的)
//感谢来自山西的大佬学妹
int etv[20];
int ltv[20];
int top = 0;
int Stack[20];//这是储存用到的栈,或者说是数组
void topuGraph(graph& Graph) {
stack<int> stack2;
for (int i = 0; i < Graph.NodeNum; i++) {
if (Graph.arr[i].in == 0)stack2.push(i);
etv[i] = 0;
}
while (!stack2.empty()) {
int temp = stack2.top();
stack2.pop();
Stack[top++] = temp;
Node* point = Graph.arr[temp].point;
while (point) {
if (--Graph.arr[point->num].in == 0) {
stack2.push(point->num);
}
if (etv[point->num]<etv[temp]+point->weight) {//修改最早数值
etv[point->num] = etv[temp] + point->weight;
}
point = point->next;
}
}
}
void keyRoad(graph& Graph) {
for (int i = 0; i < Graph.NodeNum; i++) {
ltv[i] = etv[Graph.NodeNum-1];
}
while (top >= 0) {
int temp = Stack[top--];
Node* point = Graph.arr[temp].point;
while (point) {
if (ltv[temp] > ltv[point->num] - point->weight) {
ltv[temp] = ltv[point->num] - point->weight;
}
point = point->next;
}
}
int ete, lte = 0;
for (int i = 0; i < Graph.NodeNum; i++) {
Node* point = Graph.arr[i].point;
while (point) {
ete = etv[i];
lte = ltv[point->num]-point->weight;
if (ete == lte) {
cout << i << "--->" << point->num <<"("<<point->weight<<")" << endl;
}
point = point->next;
}
}
}
|