/fucker

Some common data structures and algorigthms implemented by golang. For learning.

Primary LanguageGoMIT LicenseMIT

fucker

一些常见的数据结构与算法的golang实现。

排序(sort)

算法 时间复杂度 空间复杂度 稳定性
Bubble O( n^2 ) O(1) yes
Selection O( n^2 ) O(1) no
Heap O(nlogn) O(1) no
Insertion O(n^2) O(1) yes
Merge O(nlogn) O(n) yes
Quick O(nlogn) O(1) no
Shell O(n^(4/3)) ~ O(n^2) 取决于步长 no

  • 概念

    • 排序的稳定性(stability)

      • 如果两个相等的元素，在排序前后的相对位置保持不变，那么这是稳定的排序算法。

        排序前：5 1 3(1) 4 7 3(2)
稳定的排序：1 3(1) 3(2) 4 5 7
稳定的排序：1 3(2) 3(1) 4 5 7

        稳定的排序就是排序后第一个3还是在第二个3前面。如果两个3的相对次序交换了，则就不是稳定的排序。

    • 原地算法(In-place Algorithm)

      • 不依赖额外的资源或者依赖少数的额外资源，仅依靠输出来覆盖输入
      • 空间复杂度为O(1)的都可以认为是原地算法

树(tree)

字符串查找算法(strs)

缓存(cache)