Menu Sidebar
Menu

Algorithm

Kirchhoff’s theorem

这个算法又叫matrix tree theorem. 是一种计算一个无向图上生成树的个数的矩阵运算方法. 给一个图G, 这个图可连续也可不连续, 啥样子都可以. 设G的拉普拉斯矩阵(又名: 调和矩阵)为Q. 则我们可以通过计算Q11(删除第一行和第一列)的行列式, 得知G的生成树个数.

TimSort

TimSort其实就是插入排序和合并排序的综合体. 首先切分数组, 然后利用插入排序对小数组的优势, 先sort小数组, 然后再merge几个小数组. code我是直接抄github的

ComboSort

Combosort是一个基于swap的排序, 和冒泡排序一样, 它改良了冒泡排序中只对相邻元素做比较然后swap的特点, 通过使用gap 表示两个数时间的index位置, 然后用gap除以一个经验定值1.3,获得当前比较的两个数的位置. gap从n一直减小到1, 然后完成排序.

Bitonic Sort双调排序

这个排序的名字很好玩, Bi是双的意思 tonic是音乐的元音. 所以叫双调, 就是两个调性(递增 递减). 具体的操作可以看 https://en.wikipedia.org/wiki/Bitonic_sorter 我主要讲讲下面这个例子: [5,2,1,7,3,8,6,4], len = 8 第一步先临近的两个元素比大小, 比如[5,2]变成[2,5], [1,7]变成[7,1], 数组变为 [2,5], [7,1], [3,8], [6,4] 此时序列为[2,5,7,1,3,8,6,4] 这样就是递增, 递减, 递增 递减的两对儿双调.然后就是合并两个双调. 合并的方法是用的wiki中的batcher理论. 显示四个为一组合并, 然后是两个为一组合并. 四个为一组: [2,1,7,5] ([2,5]和[7,1]合并的结果) [6,8,3,4] ([3,8]和[6,4]合并的结果) 此时的序列为[2,1,7,5,6,8,3,4] 此时, 并不是双调序列, 还需要进行两个为一组的合并. [2,1,7,5] 变成 [1,2,5,7] 递增 [6,8,3,4] 变成 [8,6,4,3] 递减, 此时序列为[1,2,5,7,8,6,4,3] 最后要进行八个一组的合并, 然后是四个一组, 然后是两个一组. 八个一组后: [1,2,4,3,8,6,5,7] 四个一组后: [1,2,4,3,5,6,8,7] 两个一组后: […]

BeadSort重力排序

最近在看好玩的算法, 重力排序是一个根据重力(Gravity)原理的自动排序, 这个排序是自然排序的一种, 非人为操作便可实现. 这种排序非常适合给小孩子解释排序的原理和自然需求. 上面这个图就是重力排序, 首先找出最大的数, 上图中是4, 然后设为m, 就是有m个pole(杆子), 这图就是4个杆子. 然后横着看, 每个row就是当前数字有几便有几个球. 比如row 1 (ary[0] = 2) 是2, 就是两个珠子. 然后让数字随着重力下落即可排序, 具体证明和复杂度wiki有. https://en.wikipedia.org/wiki/Bead_sort 可以看出这种排序用机械实现还可以, 用算法实现效率并不好. 上面是一个实现, 具体来说, 最难的地方在于如何实现珠子下落 代码首先计算一个pole上有几个珠子, 然后计算有几个空位, 把空位补上珠子,就是下落后的个数. 最后这个算法的弱点是只能sort正整数, 而且如果数字很离散, 那么效率就太低了

Older Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

April 2021
M T W T F S S
 1234
567891011
12131415161718
19202122232425
2627282930