排序算法
-
选择排序（O(n^2)）
从i=0开始循序n次，每次从(i, n)中寻找最小的数，用minIndex记录最小值的下标，然后与a[i]的值进行交换。
for( int i=0; i<n; i++ ) {
int minIndex = i;
// 从(i, n)中寻找最小的数
for( int j=i+1 ; j<n; j++ ) {
if(a[j] < a[minIndex] ) {
minIndex = j;
}
}
swap(a[i] , a[minIndex]);//交换两个值
} -
插入排序（O(n^2)）
思路：在得到要排序的数组以后，讲数组分为两个部分，数组的第一个元素为一个部分，剩下的元素为一部分，然后从数组的第二个元素开始，和该元素以前的所有元素比较，如果之前的元素没有比该元素大的，那么该元素的位置不变，如果有元素的值比该元素大，那么记录相爱他所在的位置；例如i，该元素的位置为j，则将从i到j位置上的所有元素往后移动一位，然后将k位置上的值移动到i位置上。这样就找到了j所在的位置。每一个元素都这样进行，最终就会得到排好顺序的数组。
for( int i = 1; i < n; i++) {
for( int j = i; j > 0; j--) {
if ( a[j] < a[j-1])
swap( a[j], a[j-1];//交换两个值的位置
else
braak;
}
}这样的插入排序其实比选择排序要慢，下面来改进一下：
for( int i = 1; i < n; i++) { int t = a[i]; int j; for( j = i; j > 0 & a[j-1] > t; j--) { a[j] = a[j-1]; } a[j] = t; }改进后，在有序性非常强（近乎有序的）的数组排序下，插入排序要比选择排序更优越。
-
冒泡排序（O(n^2)）
思路：将** 相邻 **的两个数比较，将较小的数调到前头；有n个数就要进行n-1趟比较，第一次比较中要进行n-1次两两比较，在第j趟比较中，要进行n-j次两两比较。
//排序，从a[0]开始排，从小到大
for (i = 0; i < n-1; i++) {
for (j = i + 1; j < n-1-i; j++)
{
if (str[ j ] > str[ j+1 ])
{
swap(str[ j ], str[ j+1 ]);
}
}
}
-
归并排序(O(nlogn))
设两个有序的子序列(相当于输入序列)放在同一序列中相邻的位置上：array[low..m]，array[m + 1..high]，先将它们合并到一个局部的暂存序列 temp (相当于输出序列)中，待合并完成后将 temp 复制回 array[low..high]中，从而完成排序。在具体的合并过程中，设置 i，j 和 p 三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较 array[i] 和 array[j] 的关键字，取关键字较小（或较大）的记录复制到 temp[p] 中，然后将被复制记录的指针 i 或 j 加 1，以及指向复制位置的指针 p加 1。重复这一过程直至两个输入的子序列有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子序列中剩余记录依次复制到 array 中即可。
举例：-
自顶向下
转载图片.png
-
自底向上
转载图片.png
-
归并算法的优化
在数据近乎有序的情况下，插入排序依旧要快于归并排序。可以在递归的情况下修改退出递归的条件，在数据r-l小于一定数量比如15的时候，我们改为调用插入排序。
-
-
快速排序O(N*logN)
基本原理：
1.获得待排序数组a
2.选取一个合适的数字p(一般来说就选取数组或是子数组的第一个元素)作为排序基准
3.将待排序数组a中比基准p小的放在p的左边，比基准p大的放在p的右边
4.从第3步获得的两个子数组arr1跟arr2
5.判断arr1或arr2中是否只有一个元素，如果只有一个元素则返回此元素，否则就将arr1（或是arr2）代回到第1步中继续执行
注意：在几近有序的情况下，快速排序非常慢，他的深度可能原因大于logN。
-
堆排序O(N*logN)
完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。满二叉树：一颗深度为k且有2^k-1个结点的二叉树称为满二叉树。 除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上。
最大堆：根结点的键值是所有堆结点键值中最大者，且每个结点的值都比其孩子的值大。（最大堆必须是完全二叉树）
Paste_Image.png
-
索引堆
元素的值不变，只是比较元素的值，然后构建堆的时候，交换的是元素对应的索引值。举例如下：
初始时：
初始情况
构造索引堆：
最大索引堆.png
-
二叉树
-
二分查找法
用数组保存数据，保证有序。二分查找速度很快，但是仅限于查找。因为插入的时候要保证有序，所以要往后移动数据以便插入。查找复杂度 O(logn) ,插入复杂度 O(n) 。 -
二叉查找树
二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
1.若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2.任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3.任意节点的左、右子树也分别为二叉查找树。
4.没有键值相等的节点（no duplicate nodes）。-
二叉搜索树的前中后序遍历：
二叉搜索树的遍历方式.png
二叉搜索树 的查找和搜索在平均情况下时间复杂度都能达到 O(logn) ，而且能保证数据有序。 二叉搜索树 的中序遍历就是数据的顺序。如果数据是逆序，或者顺序，那么这棵树就会发生一边倒的情况使复杂度直接达到 O(n) ，就如同快排中选择到糟糕的主元(最大或者最小)。
-
广度优先遍历 （O(n)）
二叉搜索树.png
又叫宽度优先搜索或横向优先搜索，是从根结点开始沿着树的宽度搜索遍历，上面二叉树的遍历顺序为：ABCDEFG.可以利用队列实现广度优先搜索。
-
深度优先搜索
深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。以上面二叉树为例，深度优先搜索的顺序为：ABDECFG。 -
二分搜素树的结点删除
最小值：在左子树尽头
最大值：在右子叔尽头
在删除结点时，如果删除的结点有左右子树，那么应该寻找该结点右子树中的最小值结点来代替他。
-
图
-
无权图
-
有权图
-
邻接表和邻接矩阵
- 邻接表：适合表示稀疏图
- 邻接矩阵：适合表示稠密图
-
图的深度优先遍历
-
图的广度优先遍历
可以获取无权图的最短路径，闭环判断 -
最小生成树（有权图+无向图+连通图）
应用：电缆布线、电路设计、网络设计- lazy prim算法
- 优化prim算法，利用最小索引堆优化
- kruskal算法：将所有边的权值进行由小到大排序，依次选择权值小的边并且这些边之间不能构成闭环。
-
单元最短路径算法
- dijkstra算法（图中不能有负权边）
网友评论