下面是插入排序算法golang语言的实现:
一般的写法:
golang语言sort包里面的写法:
时间:
平均O(n 2 ) 最差O(n 2 ) 最好O(n)
空间:
O(1)
它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下:
时间:
平均O(n 2 ) 最差O(n 2 ) 最好O(n 2 )
空间:
O(1)
它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
时间:
平均O(n 2 ) 最差O(n 2 ) 最好O(n)
空间:
O(1)
快速排序的基本思想: 二分递归 ,通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:
我们可以通过双指针在O(n)的时间复杂度内获取合适的 j
我们设立两个指针 i 和 j,同时设置一个标志值 arr[low],一般来说,标志值取数组第一个元素
上述算法结束之后,j 所在的位置即为我们寻找的 j
4.3 时间空间复杂度
时间:
平均O(nlog 2 n) 最差O(n 2 ) 最好O(nlog 2 n)
空间:
O(1)
算法思想参考自: https://www.cnblogs.com/onepixel/articles/7674659.html
今天给大家推荐是由Social Explorer团队开源的gods框架,自称"上帝",听这个名字就很霸气,正确的解释是GoDS(Go Data Structures),是数据结构与算法相关的框架。
全能战士,该框架覆盖了数据结构与算法里,大部分容器、集合类的实现, 比golang 的标准开发包提供更丰富的数据结构。
在Go中实现各种数据结构和算法。
吸取了其他算法库数十年的知识和经验。
通过针对给定的一组问题使用最佳算法和数据结构来避免消耗内存,例如, 在TreeMap的情况下,红黑树避免在内存中保留冗余排序的键数组。
结构良好的库,具有简单的原子操作集,胜任复杂的数据操作。
保持库向后兼容
可参考的例子非常多
可以方便集成到产品中.
没有额外的导入.当实现算法的时候,我们通常要在时间效率与内存消耗之间权衡,我们选择在内存首先的情况下,不断优化得到最好的时间效率线程安全不是重点,应该在更高的应用层上处理。
囊括了列表,栈,图,树等基本数据结构 ,集合实现了HashSet, TreeSet, LinkedHashSet,列表实现ArrayList, SinglyLinkedList, DoublyLinkedList,对栈实现LinkedListStack, ArrayStack,图实现了HashMap, TreeMap, HashBidiMap, TreeBidiMap, LinkedHashMap,树实现了RedBlackTree, AVLTree, BTree,BinaryHeap,都经过性能测试的考验,值得信赖。
对于Golang开发而言,gods对底层数据结构做很好的封装,Social Explorer团队在数据处理领域,数据可视化领域有极具竞争力的产品,相信在数据处理领域有很深的积淀,才创造这么优秀的框架,由于篇幅限制,相关图片展示效果不好,感兴趣的上官网去看看。
官网: https://www.socialexplorer.com/
GitHub https://github.com/emirpasic/gods
希望大家能从emirpasic/gods学到有价值的东西。
愿我们在Go 语言的学习之路上 从此结伴而行