二叉查找树 二叉查找树，又叫二叉排序树，二叉搜索树，是一种有特定规则的二叉树，定义如下：它是一颗二叉树，或者是空树。 左子树所有节点的值都小于它的根节点，右子树所有节点的值都大于它的根节点。 左右子树也是一颗二叉查找树。二叉查找树的特点是，一直往左儿子往下找左儿子，可以找到最小的元素，一直往右儿子找右儿子，可以找到最大的元素。 看起来，我们可以用它来实现元素排序，可是我们却使用了二叉堆来实现了堆排序，...
插入排序 插入排序，一般我们指的是简单插入排序，也可以叫直接插入排序。就是说，每次把一个数插到已经排好序的数列里面形成新的排好序的数列，以此反复。 插入排序属于插入类排序算法。 除了我以外，有些人打扑克时习惯从第二张牌开始，和第一张牌比较，第二张牌如果比第一张牌小那么插入到第一张牌前面，这样前两张牌都排好序了，接着从第三张牌开始，将它插入到已排好序的前两张牌里，形成三张排好序的牌，后面第四张牌继续插入...
希尔排序 1959 年一个叫Donald L. Shell (March 1, 1924 – November 2, 2015)的美国人在Communications of the ACM 国际计算机学会月刊发布了一个排序算法，从此名为希尔排序的算法诞生了。 注：ACM = Association for Computing Machinery，国际计算机学会，世界性的计算机从业员专业组织，创立于1947年，是世界上第一个科学性及教育性计算机学会。 希尔排序是直接插入排序的改进版本。因为直接插入排序对那些几乎已经排好序的数...
排序算法 人类的发展中，我们学会了计数，比如知道小明今天打猎的兔子的数量是多少。另外一方面，我们也需要判断，今天哪个人打猎打得多，我们需要比较。 所以，排序这个很自然的需求就出来了。比如小明打了5只兔子，小王打了8只，还有部落其他一百多个人也打了。我们要论功行赏，谁打得多，谁就奖赏大一点。 如何排序呢，怎么在最快的时间内，找到打兔子最多的人呢，这是一个很朴素的问题。 经过很多年的研究，出现了很多的排序算...
选择排序 选择排序，一般我们指的是简单选择排序，也可以叫直接选择排序，它不像冒泡排序一样相邻地交换元素，而是通过选择最小的元素，每轮迭代只需交换一次。虽然交换次数比冒泡少很多，但效率和冒泡排序一样的糟糕。 选择排序属于选择类排序算法。 我打扑克牌的时候，会习惯性地从左到右扫描，然后将最小的牌放在最左边，然后从第二张牌开始继续从左到右扫描第二小的牌，放在最小的牌右边，以此反复。选择排序和我玩扑克时的排序...
栈和队列 一、栈 Stack 和队列 Queue 我们日常生活中，都需要将物品排列，或者安排事情的先后顺序。更通俗地讲，我们买东西时，人太多的情况下，我们要排队，排队也有先后顺序，有些人早了点来，排完队就离开了，有些人晚一点，才刚刚进去人群排队。 数据是有顺序的，从数据1到数据2，再到数据3，和日常生活一样，我们需要放数据，也需要排列数据。 在计算机的世界里，会经常听见两种结构，栈（stack）和队列 (queue)。它们是一种收...
常见数据结构及算法 数据结构主要用来组织数据，也作为数据的容器，载体。 各种各样的算法，都需要使用一定的数据结构来组织数据。 常见的典型数据结构有：链表 栈和队列 树 图上述可以延伸出各种各样的术语和结构，如列表，集合，哈希表，堆，优先队列，二叉树，红黑树，B+树以及各种变种等。 我们区别开数据结构和算法，是因为算法是更高层次的一种智慧结晶，目的就是为了解决问题，基本的算法分类有：排序算法 查找算法 图相关的...
树 树是一种比较高级的基础数据结构，由n个有限节点组成的具有层次关系的集合。 树的定义：有节点间的层次关系，分为父节点和子节点。 有唯一一个根节点，该根节点没有父节点。 除了根节点，每个节点有且只有一个父节点。 每一个节点本身以及它的后代也是一棵树，是一个递归的结构。 没有后代的节点称为叶子节点，没有节点的树称为空树。二叉树：每个节点最多只有两个儿子节点的树。 满二叉树：叶子节点与叶子节点之间的高度差为0的...
2-3-4树和普通红黑树 某些教程不区分普通红黑树和左倾红黑树的区别，直接将左倾红黑树拿来教学，并且称其为红黑树，因为左倾红黑树与普通的红黑树相比，实现起来较为简单，容易教学。在这里，我们区分开左倾红黑树和普通红黑树。 红黑树是一种近似平衡的二叉查找树，从2-3树或2-3-4树衍生而来。通过对二叉树节点进行染色，染色为红或黑节点，来模仿2-3树或2-3-4树的3节点和4节点，从而让树的高度减小。2-3-4树对照实现的红黑树是普...
package mainimport "fmt"func main() {src := []int{1, 3, 493, 0, 2, 55, -92, 8, 23, -19, -19}quick_sort(src, 0, len(src)-1)fmt.Println(src) }func quick_sort(src []int, left int, right int) {if left >= right {return}i := leftj := rightt := src[left] // 基准值for i < j {// 找到比基准值小的元素for src[j] > t && i < j {j--}// 找到比基准值大的元素for src[i] <= t && i < j {i++}// 交换if i < j {temp := sr...
package mainimport "fmt"// Send the sequence 2, 3, 4, ... to channel 'ch'. func generate(ch chan int) {for i := 2; ; i++ {ch <- i // Send 'i' to channel 'ch'.} }// Copy the values from channel 'in' to channel 'out', // removing those divisible by 'prime'. func filter(in, out chan int, prime int) {for {i := <-in // Receive value of new variable 'i' from 'in'.if i%prime != 0 {out <- i // Send 'i' to...
会了上一个，这个就差不离了。 StackLinkedList.gopackage StackLinkedListtype Node struct {data intnext *Node }type Stack struct {top *Node }func (list *Stack) Push(i int) {data := &Node{data: i}if list.top != nil {data.next = list.top}list.top = data }func (list *Stack) Pop() (int, bool) {if list.top == nil {return 0, false}i := list.top.datalist.top = list.top.nextreturn i, true }func (list *Stack)...
package mainimport "fmt"func main() { matrix := [][]int{ {1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}, } exist := searchMatrix(matrix, 5) fmt.Println("exit", exist)}func searchMatrix(matrix [][]int, target int) bool { if matrix == nil || len(matrix) == 0 || len(matrix[0]) == 0 { return false } row := 0 col := len(matrix[0])...
概括 Go的垃圾回收官方形容为 非分代 非紧缩 写屏障 三色并发标记清理算法。非分代：不像Java那样分为年轻代和年老代，自然也没有minor gc和maj o gc的区别。非紧缩：在垃圾回收之后不会进行内存整理以清除内存碎片。写屏障：在并发标记的过程中，如果应用程序（mutator）修改了对象图，就可能出现标记遗漏的可能，写屏障就是为了处理标记遗漏的问题。三色：将GC中的对象按照搜索的情况分成三种： 黑色: 对象在这次GC中已标记,且这...
Letter Combinations of a Phone Number Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below.Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].Note:Although the above answer is in lexicographical order, your answer could be in any order you ...