Conzxy's blog

归并排序基本思路归并排序的基本思想是：首先将a[0..n-1]看成是n个长度为1的有序表，将相邻的k（k≥2）个有序子表成对归并，得到n/k个长度为k的有序子表；然后再将这些有序子表继续归并，得到n/k2个长度为k2的有序子表，如此反复进行下去，最后得到一个长度为n的有序表。若k=2，即归并在相邻的两个有序子表中进行的，称为二路归并排序。若k>2，即归并操作在相邻的多个有序子表中进行，则叫多路归并排序。 归并排序体现的就是分治思想。 自顶而下的排序步骤： 分解：将[low,high]分解成两个子表，即求mid=（low+high)/2,然后继续对[low,mid],[mid+1,high]分解，直至子表长度为1终止（因为长度为1的子表一定是有序的） 归并：将排序好的两个子表[low,mid],[mid+1,high]合并 实现代码123456789101112131415161718192021222324252627282930void Merge(List &L,int low,int mid,int high){ int i=low,j=mid+ ...

插入排序直接插入排序直接插入排序就是无序区有和有序区反序的元素，那么就将这个元素插入到有序区中合适的位置，使之成为有序区的元素 实现代码1234567891011121314151617void InsertSort(List &L){ int i,j; int temp; for(i=1;i<L.size;i++) { if(L[i-1]>L[i]) //发现反序元素 { temp=L[i]; //临时变量记住要插入的元素 for(j=i-1;j>=0&&L[j]>temp;j--) { L[j+1]=L[j]; //将有序区中比temp大的都右移，让出位置 } L[j+1]=temp; //注意之前for的j-- } }} 算法复杂度最好的情况（全都正序）：比较次数 ...

堆排序基本概念堆，分为大（顶）堆和小（顶）堆，是顺序存储的完全二叉树，并且满足一下特性之一：(1) 任意非终端结点关键字不小于左右子结点（大堆） ki >= k2i+1并且ki>=k2i+2 其中，0 <= i <= (n-1)/2，n是数组元素个数 (2) 任意非终端结点关键字不大于左右子结点（小堆） ki <= k2i+1并且ki<=k2i+2 其中，0 <= i <= (n-1)/2，n是数组元素个数 调整从当前结点（要求是非终端结点）开始，对于大堆，要求当前结点关键字不小于子结点，如不符合，则将最大的子结点与当前结点交换。循环迭代交换后的子树，确保所有子树都符合大堆特性。小堆类似 基本思想堆排序就是利用构建堆和输出堆顶元素的过程，不断对堆进行调整以保证当前结点及其孩子结点满足堆特性，从而达到对初始数组元素进行排序的目的。核心步骤： 1)构建堆（大堆/小堆） 从最后一个非终端结点开始，向前进行调整，保证当前结点及其子树符合堆特性； 2)输出有序序列 交换堆顶与末尾叶子结点，堆顶输出到数组的有序序列末尾，而 ...

计数排序基本思想计数排序是一种线性排序算法，它利用了一个数组，因为数组下标的增长是线性的，所以它就把自己的元素转换成新开辟数组的下标。但是数组元素有正有负，下标只有非负值，那么我们就应该考虑如何转换。这也不是很难，只要我们将该元素值减去数组最小值即可得到count数组的下标（类似映射函数）。 例子用数组元素减去数组最小值即可得到在count数组的下标。count数组中用橙色框住的表示待排序数组转换后的元素不存在。同时，可以观察到count数组的大小是max-min+1=8+6+1=15.将count中对应原数组的元素放回数组即可 实现代码1234567891011121314151617181920212223242526272829303132void CountSort(List &L){ int i; int min=L[0],max=L[0]; for(i=1;i<L.size;i++) { if(L[i]>max) { max=L[i]; } ...

桶排序基本思想桶排序的思想近乎彻底的分治思想。桶排序假设待排序的一组数均匀独立的分布在一个范围中，并将这一范围划分成几个子范围（桶）。然后基于某种映射函数f ，将待排序列的关键字 k 映射到第i个桶中 (即桶数组B 的下标i) ，那么该关键字k 就作为 B[i]中的元素 (每个桶B[i]都是一组大小为N/M 的序列 )。接着将各个桶中的数据有序的合并起来 : 对每个桶B[i] 中的所有元素进行比较排序 (可以使用快排)。然后依次枚举输出 B[0]….B[M] 中的全部内容即是一个有序序列。补充： 映射函数一般是 f = array[i] / k; k^2 = n; n是所有元素个数为了使桶排序更加高效，我们需要做到这两点： 在额外空间充足的情况下，尽量增大桶的数量 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中 同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。 实现代码12345678910111213141516171819202122232425262728293031323334void BucketSort(List &L) ...

冒泡排序基本思想冒泡排序分为趟数和交换次数。外层循环为趟数，如果有n个元素则要循环n-1趟。内层循环主要做每一趟的交换，从第0个元素开始如果发现当前元素大于它的后一个元素，将其交换，每一趟下来，前面的有序区新增一个最小值（相比无序区最小），然后在无序区的第一个元素开始到最后一个元素冒泡排序，将最小值冒出来，以此循环。 最简单的版本123456789101112void BubbleSort(List &L){ int i,j; for(i=0;i<L.size-1;i++) { for(j=i+1;j<L.size;j++) { if(L[i]>L[j]) swap(L[i],L[j]); } }} 严格意义上，这并不能称得上冒泡排序，因为不是比较两个相邻元素，而是直接拿第i个元素和第j个元素对比，这样的话对第i个元素之后的序列没什么帮助。 第一层优化1234567891011121314void BubbleSort_each(List &L ...

并查集（Union-Find Set）概念并查集正如其名，分为Union和Find,即合并和查找。 代表元我们用集合中某个元素来代表这个集合，称为代表元。一个集合中的所有元素形成以代表元为根结点的树形结构。对于每一个元素parent[x]指向x在树形结构中的父节点，如果x是根结点，则令parent[x]=x。 查找操作(Find)就是依据parent[x]一路往上爬，最后找到代表元，从而确定自己所在的集合。 路径压缩（查找优化）为了加快查找速度，我们把x到根结点上的路径上的所有结点的parent都设为根结点。 合并（Union）连接两个非连通块，成为新的连通块，其中一个根结点成为新块的根结点。 基本操作一般，并查集分三个操作 初始化对所有单个数据建立一个单独的集合（即根据题目的意思自己建立的最多可能有的集合，为下面的合并查找操作提供操作对象）一般来说，每一个单个的集合有三个要素： 集合所代表的数据（自定义） 集合的层次，用rank表示（初始化一般将rank都初始化为0） 集合的类别，用parent或是set表示（用指针指示） 有的题里面集合的数据就是这个集合的标号，也就是说只包含2 ...

判断有向树有向树的特征 根的入度为0，其他均为1 不能成环 只能有一个根 思路用并查集来解决该问题是最好的。 init 初始化 Union 合并操作(包含成环判断) Find 查找操作 唯一根结点检查 root_check 入度检查 degree_check 实现代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374bool flag=true; //有向树标志const int maxs = 1e6+5; int fa[maxs], degree[maxs]; //全局数组set<int> s;set<int>::iterator it;int Find(int x) //寻找父节点 { return fa[x]==x?x:(fa[x]=Find(fa[x])); ...

Kruskalkruskal与prim不同，是基于边去构造最小生成树，所以适用于边比较少的稀疏图。kruskal需要边的集合，我们称其为边集数组。边集数组按从小到大的顺序排序，方便构造最小生成树。 边集数组结构体12345struct edge { int begin, end, weight; bool operator<(edge const& rhs) {return this->weight < rhs.weight;}}edges[maxsize * (maxsize - 1)];边集数组构造函数123456789101112void get_edges_set(){ int a = 0; for (int i = 0; i < nume; i++) { cin >> u >> v >> w; edges[a].begin = u - 'A'; edge ...

DijkstraDijkstra是一种求得从一个顶点出发到达终点最短路径的算法。Dijkstra本质就是贪心算法，它不是一次求得从起点到终点的最短路径，而是一步步求得它们之间顶点的最短路径，基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到你要的结果。 引入概念点权：点权值就是源点到该顶点的最短路径（贪心算法必然的结果），下面的D和dist都是存储点权值的vector，将它们输出可以得到源点到各顶点的最短路径。 Dijkstra实现关键——松弛操作松弛操作是Dijkstra算法的基础操作：如果存在一条从u到v的边，那么从s到v的一条新路径是将边 w(u,v)添加到从s到u的路径尾部来拓展一条从s到v的路径。这条路径的长度是d[u]+w(u,v)。如果这个值比目前已知的d[v]的值要小，那么可以用这个值来替代当前d[v]中的值。松弛边的操作一直运行到所有的d[v]都代表从s到v的最短路径的长度值。松弛操作正是贪心算法的体现。PS:d[x]表示的是源点到x的最短路径。 基本思想 将起点权值置为0，其他顶点置为无穷大 集合A装所有顶点 while A不为空时pop出A中最小权值 ...