排序_快速排序
简述 快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移到数列一边，比它小的元素移到数列的另一边，从而把数列拆解成两个部分。 快速排序是从冒泡排序演变而来的。 快速排序也属于交换排序，通过元素之间的比较和交换位...
大话数据结构_算法相关&&AVL&&B树相关 5
时间复杂度 O(1) O(logn) O(n) O(nlogn) O(n^2) O(n^3) O(2^n) O(n!) O(n^n) $$ O(1) < O(log_n)<O(n)<O(nlog_n...
排序_冒泡排序
简述 冒泡排序通过反复遍历要排序的列表，比较每对相邻项，并以升序或降序的方式交换它们。重复操作列表，知道不需要交换为止。 复杂度 名称 最好 平均 最差 空间 稳定性 冒泡排序 n n2 n2 1 是 理解 冒泡排序...
排序_堆排序
二叉堆 特性 最大堆的堆顶是整个堆中的最大元素 最小堆的堆顶是整个堆中的最小元素 每次删除旧堆顶，调整后的新堆顶都是大小仅次于旧堆顶的节点。 只要反复删除堆顶，反复调整二叉堆，所得到的集合就会成为一个有序集合。 简述...
基础算法模板
快速排序 void quick_sort(int q[], int l, int r) { if (l >= r) return; int i = l - 1, j = r + 1, x = q[l + r &...
匹配_KMP模式匹配算法：一
模式匹配 对子串的定位操作通常被称为串的模式匹配 简单的说，就是对主串S的每一个字符作为子串开头，与要匹配的字符串T进行匹配，对主串S做大循环，每个字符开头做T的长度的小循环，直到匹配成功或者全部遍历完成为止 朴素的...
数学知识模板
试除法判定质数 bool is_prime(int x) { if (x < 2) return false; for (int i = 2; i <= x / i; i ++ ) if (x % i =...
查找_二分查找
简述 也叫折半查找，性能优异。 但是所查找的数列必须是有序序列。 复杂度 时间复杂度 log2(N) 实现 非递归实现 int BinarySearch(int array[],int key,int length)...
排序_桶排序
简述 桶排序需要创建若干个桶来协助排序。 所谓桶，每个桶bucket代表一个区间范围，里面可以承载一个或多个元素。 复杂度 名称 最好 平均 最差 空间 稳定性 桶排序 n+k n nlog(n) n 是 实现 vo...
匹配_有限自动机字符串匹配算法
定义 假设文本是一个长度为n的数组 T[1...n]，而模式是一个长度为m的数组P[1...m]，其中m<=n。进一步假设P和T的元素都是来自一个有限字母集合M的字符。如M={0,1}或者M={a,b,c,.....