上一章的算法笔记，并不算一个算法系列的一个合适的開始。而本章将会介绍一种产生随机全排列的方法，下一章開始，就正式開始我们的排序算法了。在我们的排序算法演示器中，我们须要一组随机的数据来作为排序的開始，而本章，就会产生这么一组随机数据。（一）实现分析我们须要一组随机的数据，并且似乎产生的方法不会太难。我们仅仅须要通过rand()函数获得一个随机数，让其对count（排序的规模）取模，结果作为数组的索引，其值是当...
/// <summary>/// 步骤:/// 1.记录当前待排元素/// 2.标记顺序表有序查找区域下界和上界/// 3.在顺序表有序查找区域中折半查找等待排序元素的位置/// 4.把顺序表有序查找区域的某些元素后移一位，以空出位置给等待排序的元素/// 5.在空出的位置填写当前排序元素/// </summary>/// <param name="elements"></param>staticvoid SqListSort(int[] elements) {int low; // 有序区域下界int mid; // 有序区域中界int high;// 有序...
pair的常见用法pair是一个很实用的“小玩意”，当想要将两个元素绑在一起作为一个合成元素、又不想要因此定义结构体时，使用pair可以很方便地作为一个代替品。也就是说，pair实际上可以看作一个内部有 两个元素的结构体，且这两个元素的类型是可以指定的，如下面的短代码所示：struct pair{typeName1 first;typeName2 second; } pair的定义头文件#include<utility> using namespace std; 因为实现map时候已经使用了pair，所以...
二叉查找树 查找插入性能有序性相关的操作 最大键、最小键向上取整、向下取整选择、排名范围查找删除操作 删除最大键、最小键通用删除操作二叉查找树前面了解的无序链表和有序数组在性能方面至少在线性级别，无法用于数据量大的场合。接下来要学习的二叉查找树可以将链表插入的灵活性和有序数组查找的高效性结合起来，是计算机科学中最重要的算法之一。 一个二叉查找树（Binary Search Tree）是一颗二叉树，其中每个结点都含有一个...
这篇博客源于最近正在准备的面试。XX的 一个笔试题。在这简单总结一下。如题：请用任意语言，完成至少一种算法。从数据结构 软考和实际的应用中我们都有了 一定的理解。今天我们开看看。话不多说，直接贴代码。选择排序：插入排序：其实到现在，这样的代码也都很简单，平时也应该多回顾多复习一下。版权声明：本文为博主原创文章，未经博主允许不得转载。原文：http://blog.csdn.net/u010176014/article/details/46684115
一、对堆排序的相关了解1、堆排序的运行时间是 O(nlogn) ；2、定义：堆heap是一棵具有以下属性的二叉树——（1）它是一棵完全二叉树；（2）每个结点大于或等于它的任意一个孩子。 备注：完全二叉树的定义——除了最后一层没填满以及最后一层的叶子都是偏左放置的，其他层都是满的二叉树！ 3、二叉堆有两种：最大堆和最小堆。在堆排序中我们使用的是最大堆，最小堆常常在构造优先队列时使用。 ...
#include <stdio.h> constint maxn = 100; int a[maxn] = {0}; int b[maxn]= {0}; int main(void) {int n;while(scanf("%d", &n) != EOF){for(int i=0; i<n; i++){scanf("%d", a+i);}int m;scanf("%d", &m);int j;for(int i=0; i<m; i++){scanf("%d", b+i);for(j=0; j<n; j++){if(a[j] == b[i]) break;}if (j==n) printf("NO\n");else printf("YES\n");}} } 原文：https://www.cnblogs.com/acoccus/p/10074074.html
模板：struct Circle_Square_Tree {const static int N = 2e4 + 10;vector<pair<int, LL> > G[N];int dp[N], anc[N][18], n;LL dis[N], cir[N]; //环的大小bool vis[N];//记录到方点的最短距离是否经过回边vector<pii> g[N];int dfn[N], low[N], fa[N], cnt, tot;int a[N];inline void solve(int u, int v, int d) {int cnt = 0;LL sum = d;for (int i = v; i != u; i = fa[i]) sum += dis[i] - dis[fa[i]], a[++cnt] = i;a[++cnt]...
10.1 图的定义和相关术语图由顶点和边组成，每条边的两端都必须是图的两个顶点。而记号G(V,E)表示图G的顶点集为V、边集为E。一般来说，图可分为有向图和无向图。有向图的所有边都有方向，即确定了顶点到顶点的一个指向；而无向图的所有边都是双向的，即无向边所连接的两个顶点可以互相到达。 10.2 图的存储一般来说，图的存储方式有两种：邻接矩阵和邻接表。10.2.1 邻接矩阵令二维数组G[N][N]的两维分别表示图的顶点标号，即如果G[...
Kosaraju算法详见《挑战程序设计竞赛》p320模板：constint N=1e5+5; int n,m; vector<int>g[N]; vector<int>rg[N]; vector<int>vs; bool vis[N]; int cmp[N];void add_edge(int u,int v) {g[u].pb(v);rg[v].pb(u); } void dfs(int u) {vis[u]=true;for(int i=0;i<g[u].size();i++)if(!vis[g[u][i]])dfs(g[u][i]);vs.pb(u); }void rdfs(int u,int k) {vis[u]=true;cmp[u]=k;for(int i=0;i<rg[u].size();i++)if(!vis[rg[u][i]])rdfs(...
目录1 问题描述2 解决方案2.1 蛮力法 1 问题描述何为旅行商问题？按照非专业的说法，这个问题要求找出一条n个给定的城市间的最短路径，使我们在回到触发的城市之前，对每个城市都只访问一次。这样该问题就可以表述为求一个图的最短哈密顿回路的问题。（哈密顿回路：定义为一个对图的每个顶点都只穿越一次的回路） 很容易看出来，哈密顿回路也可以定义为n+1个相邻顶点v1,v2,v3,...,vn,v1的一个序列。其中，序列的第一个顶点和最后一...
链式前向星这个博客写的不错：http://www.cnblogs.com/Tovi/p/6194786.html模板：①add_edge void add_edge(int u,int v,int w) {edge[cnt].to=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++; } ②遍历以u节点为起点的所有边 for(int i=head[u];~i;i=edge[i].next) 原文：http://www.cnblogs.com/widsom/p/7637359.html
加权有向图数据结构 加权有向边加权有向图最短路径边的松弛Dijkstra算法地图或者导航系统是最短路径的典型应用，其中顶点对应交叉路口，边对应公路，边的权重对应经过一段路的成本（时间或距离）。在这个模型中，问题可以被归纳为：找出从一个顶点到达另一个顶点的成本最小的路径。此外，网络路由、任务调度等也属于同类问题。加权有向图加权有向图是研究最短路径问题的模型。在加权有向图中，每条有向边都有一个与之关联的权重，路...
目录1 海盗分金币2 六角幻方3 格子放鸡蛋4 排列序数5 幂一矩阵6 供水设施 1 海盗分金币有5个海盗，相约进行一次帆船比赛。比赛中天气发生突变，他们被冲散了。恰巧，他们都先后经过途中的一个无名的荒岛，并且每个人都信心满满，觉得自己是第一个经过该岛的人。第一个人在沙滩上发现了一堆金币。他把金币分成5等份。发现刚好少一个金币。他就从自己口袋拿出一个金币补充进去，然后把属于自己的那份拿走。第二个到达的人也看到了金币...
目录1 问题描述2 解决方案2.1 选择排序原理简介2.2 具体编码（选择排序）2.3 冒泡排序原理简介 2.4 具体编码（冒泡排序） 1 问题描述给定一个可排序的n元素序列（例如，数字、字符和字符串），将它们按照非降序方式重新排列。2 解决方案2.1 选择排序原理简介选择排序开始的时候，我们从第一个元素开始扫描整个列表，找到它的最小元素，然后和第一个元素交换，将最小元素和第一个元素交换位置；然后，我们从第二个元素开始扫描剩下的...