05-前缀树、桶排序、排序总结.md

[TOC]
# 1 前缀树结构(trie)、桶排序、排序总结

## 1.1 前缀树结构

- 单个字符串中，字符从前到后的加到一颗多叉树上
- 字符放在路上，节点上有专属的数据项(常见的是pass和end值)
- 所有样本都这样添加。如果没有路就新建，如果有路就复用
- 沿途节点的pass值增加1.每个字符串结束时来到的节点end值增加1
 一个字符串数组中，所有字符串的字符数为N,整个数组加入前缀树种的代价是O(N)

功能一：构建好前缀树之后，我们查询某个字符串在不在前缀树中，某字符串在这颗前缀树中出现了几次都是特别方便的。例如找"ab"在前缀树中存在几次，可以先看有无走向a字符的路径(如果没有，直接不存在)，再看走向b字符的路径，此时检查该节点的end标记的值，如果为0，则前缀树中不存在"ab"字符串，如果e>0则，e等于几则"ab"在前缀树种出现了几次

功能二：如果单单是功能一，那么哈希表也可以实现。现查询所有加入到前缀树的字符串，有多少个以"a"字符作为前缀，来到"a"的路径，查看p值大小，就是以"a"作为前缀的字符串数量

```Go
package main

// Node 前缀树的节点
type Node struct {
	Pass    int
	End     int
	Childes []*Node
}

func NewTrie() (root *Node) {
	trie := &Node{
		Pass: 0,
		End:  0,
		// 默认保存26个英文字符a~z
		// 0 a
		// 1 b
		// .. ..
		// 25 z
		// Childes[i] == nil 表示i方向的路径不存在
		Childes: make([]*Node, 26),
	}
	return trie
}

// Insert 往该前缀树中添加字符串
func (root *Node) Insert(word string) {
	if len(word) == 0 {
		return
	}
	// 字符串转字符数组,每个元素是字符的ascii码
	chs := []byte(word)
	node := root
	// 头结点的pass首先++
	node.Pass++
	// 路径的下标
	var path int
	// 从左往右遍历字符
	for i := 0; i < len(chs); i++ {
		// 当前字符减去'a'的ascii码得到需要添加的下个节点下标。即当前字符去往的路径
		path = int(chs[i] - 'a')
		// 当前方向上没有建立节点，即一开始不存在这条路，新开辟
		if node.Childes[path] == nil {
			node.Childes[path] = &Node{
				Pass:    0,
				End:     0,
				Childes: make([]*Node, 26),
			}
		}
		// 引用指向当前来到的节点
		node = node.Childes[path]
		// 当前节点的pass++
		node.Pass++
	}
	// 当新加的字符串所有字符处理结束，最后引用指向的当前节点就是该字符串的结尾节点，end++
	node.End++
}

// Search 在该前缀树中查找word这个单词之前加入过几次
func (root *Node) Search(word string) int {
	if len(word) == 0 {
		return 0
	}
	chs := []byte(word)
	node := root
	index := 0
	for i := 0; i < len(chs); i++ {
		index = int(chs[i] - 'a')
		// 寻找该字符串的路径中如果提前找不到path，就是未加入过，0次
		if node.Childes[index] == nil {
			return 0
		}
		node = node.Childes[index]
	}
	// 如果顺利把word字符串在前缀树中走完路径，那么此时的node对应的end值就是当前word在该前缀树中添加了几次
	return node.End
}

// Delete 删除该前缀树的某个字符串
func (root *Node) Delete(word string) {
	// 首先要查一下该字符串是否加入过
	if root.Search(word) != 0 {
		// 沿途pass--
		chs := []byte(word)
		node := root
		node.Pass--
		path := 0
		for i := 0; i < len(chs); i++ {
			path = int(chs[i] - 'a')
			// 在寻找的过程中，pass为0，提前可以得知在本次删除之后，该节点以下的路径不再需要，可以直接删除。
			// 那么该节点之下下个方向的节点引用置为空（JVM垃圾回收，相当于该节点下的路径被删了）
			node.Childes[path].Pass--
			if node.Childes[path].Pass == 0 {
				node.Childes[path] = nil
				return
			}
			node = node.Childes[path]
		}
		// 最后end--
		node.End--
	}
}

// PrefixNumber 所有加入的字符串中，有几个是以pre这个字符串作为前缀的
func (root *Node) PrefixNumber(pre string) int {
	if len(pre) == 0 {
		return 0
	}

	chs := []byte(pre)
	node := root
	index := 0
	for i := 0; i < len(chs); i++ {
		index = int(chs[i] - 'a')
		// pre走不到最后，就没有以pre作为前缀的字符串存在
		if node.Childes[index] == nil {
			return 0
		}
		node = node.Childes[index]
	}
	// 顺利走到最后，返回的pass就是有多少个字符串以当前pre为前缀的
	return node.Pass
}
```

> Trie的孩子Childes，可以用一个map实现。可以容纳针对各种字符串的情况，实现自由扩展，make(map[int]*Node)，表示字符的ascii码对应的节点映射。此处略


## 1.2 不基于比较的排序-桶排序

> 例如：一个代表员工年龄的数组，排序。数据范围有限，对每个年龄做词频统计。arr[0~200] = 0,M=200

> 空间换时间

### 1.2.1 计数排序

桶排序思想下的排序：计数排序 & 基数排序:

1、 桶排序思想下的排序都是不基于比较的排序

2、 时间复杂度为O(N),二维空间复杂复杂度为O(M)

3、 应用范围有限，需要样本的数据状况满足桶的划分

> 缺点：与样本数据状况强相关。

### 1.2.2 基数排序

> 应用条件：十进制数据，非负

如果对：[100,17,29,13,5,27] 进行排序：

1、找最高位的那个数的长度，这里100的长度为3，其他数前补0，得出 [100,017,029,013,005,027]

2、 准备10个桶，对应的数字0~9号桶，每个桶是一个队列。根据样本按个位数字对应进桶，相同个位数字进入队列，再从0号桶以此倒出，队列先进先出。个位进桶再依次倒出，得出 [100,013,005,017,027,029]

3、 再把按照个位进桶倒出的样本，再按十位进桶，再按相同规则倒出得 [100,005,013,017,027,029]

4、再把得到的样本按百位进桶，倒出得 [005,013,017,027,029,100]

此时达到有序！

> 思想：先按各位数字排序，各位数字排好序，再用十位数字的顺序去调整，再按百位次序调整。优先级依次递增，百位优先级最高，百位优先级一样默认按照上一层十位的顺序...

**结论：基于比较的排序，时间复杂度的极限就是O(NlogN)，而不基于比较的排序，时间复杂度可以达到O(N)。在面试或刷题，估算排序的时间复杂度的时候，必须用基于比较的排序来估算**

```Go
package main

import "math"

// BucketSort 计数排序
func BucketSort(arr []int) {
	if len(arr) < 2 {
		return
	}

	max := math.MinInt
	for i := 0; i < len(arr); i++ {
		max = int(math.Max(float64(max), float64(arr[i])))
	}

	bucket := make([]int, max+1)
	for i := 0; i < len(arr); i++ {
		bucket[arr[i]]++
	}
	k := 0
	for i := 0; i < len(bucket); i++ {
		bucket[i]--
		for bucket[i] > 0 {
			arr[k] = i
			k++
		}
	}
}
```

> 下面代码的思想：

> 例如原数组[101,003,202,41,302]。得到按个位的词频conut数组为[0,2,2,1,0,0,0,0,0,0]。通过conut词频累加得到conut'为[0,2,4,5,5,5,5,5,5,5],此时conut'的含义表示个位数字小于等于0的数字有0个，个位数字小于等于1的有两个，个位数字小于等于2的有4个......

> 得到conut'之后，对原数组[101,003,202,41,302]从右往左遍历。根据基数排序的思想，302应该是2号桶最后被倒出的，我们已经知道个位数字小于等于2的有4个，那么302就是4个中的最后一个，放在help数组的3号位置,相应的conut'小于等于2位置的词频减减变为3。同理，41是1号桶的最后一个，个位数字小于等于1的数字有两个，那么41需要放在1号位置，小于等于1位置的词频减减变为1，同理......

> 实质增加conut和count'结构，避免申请十个队列结构，不想炫技直接申请10个队列结构，按基数排序思想直接做没问题

> 实质上，基数排序的时间复杂度是O(Nlog10max(N)),log10N表示十进制的数的位数，但是我们认为基数排序的应用样本范围不大。如果要排任意位数的值，严格上就是O(Nlog10max(N))

```Go
package main

import "fmt"

func RadixSort(nums []int) []int  {
	numberBit := howManyBit(maximum(nums))
	// 循环的次数
	// 定义一个rec 二维切片 rec[i][x] 用来接受尾数是 i的数字
	for i := 0; i < numberBit; i++ {
		rec := make([][]int, 10)

		for _, num := range nums {
			rec[(num/pow10(i))%10] = append(rec[(num/pow10(i))%10], num)
		}
		// flatten the rec slice to the one dimension slice
		numsCopy := make([]int, 0)
		for j := 0; j < 10; j++ {
			numsCopy = append(numsCopy, rec[j]...)
		}
		// refresh nums，使得他变为 经过一次基数排序之后的数组
		nums = numsCopy
	}
	return nums
}

func pow10(num int) int {
	res := 1
	base := 10
	for num != 0 {
		if num&1 ==1 {
			num -= 1
			res *= base
		}
		num >>= 1
		base *= base
	}
	return res
}

func maximum(list []int) int {
	max := 0
	for _, i2 := range list {
		if i2 > max {
			max = i2
		}
	}
	return max
}

func howManyBit(number int) int  {
	count := 0
	for number != 0 {
		number = number/10
		count += 1
	}
	return count
}

func main() {
	var theArray = []int{10, 1, 18, 30, 23, 12, 7, 5, 18, 233, 144}
	fmt.Print("排序前")
	fmt.Println(theArray)
	fmt.Print("排序后")
	fmt.Println(RadixSort(theArray))
}
```

## 1.3 排序算法的稳定性

> 稳定性是指同样大小的样本在排序之后不会改变相对次序。基础类型稳定性没意义，用处是按引用传递后是否稳定。比如学生有班级和年龄两个属性，先按班级排序，再按年龄排序，那么如果是稳定性的排序，不会破坏之前已经按班级拍好的顺序

> 稳定性排序的应用场景：购物时候，先按价格排序商品，再按好评度排序，那么好评度实在价格排好序的基础上。反之不稳定排序会破坏一开始按照价格排好的次序


### 1.3.1 稳定的排序

1、 冒泡排序（处理相等时不交换）

2、 插入排序（相等不交换）

3、 归并排序（merge时候，相等先copy左边的）

### 1.3.2 不稳定的排序

1、 选择排序

2、 快速排序 （partion过程无法保证稳定）

3、 堆排序 （维持堆结构）

### 1.3.3 排序稳定性对比

排序 | 时间复杂度 | 空间复杂度 | 稳定性
---|---|---|---
选择排序 | O(N^2) | O(1) | 无
冒泡排序 | O(N^2) | O(1) | 有
插入排序 | O(N^2) | O(1) | 有
归并排序 | O(NlogN) | O(N) | 有
随机快拍 | O(NlogN) | O(logN) | 无
堆排序 | O(NlogN) | O(1) | 无
计数排序 | O(N) | O(M) | 有
堆排序 | O(N) | O(N) | 有


## 1.4 排序算法总结

1. 不基于比较的排序，对样本数据有严格要求，不易改写
2. 基于比较的排序，只要规定好两个样本怎么比较大小就可以直接复用
3. 基于比较的排序，时间复杂度的极限是O(NlogN)
4. 时间复杂度O(NlogN)、额外空间复杂度低于O(N)，且稳定的基于比较的排序是不存在的
5. 为了绝对的速度选择快排（快排的常数时间低），为了节省空间选择堆排序，为了稳定性选归并

## 1.5 排序常见的坑点

> 归并排序的额为空间复杂度可以变为O(1)。“归并排序内部缓存法”，但是将会变的不稳定。不考虑稳定不如直接选择堆排序

> “原地归并排序”是垃圾帖子，会让时间复杂度变成O(N ^2)。时间复杂度退到O(N ^2)不如直接选择插入排序

> 快速排序稳定性改进，“01 stable sort”，但是会对样本数据要求更多。对数据进行限制，不如选择桶排序

> 在整形数组中，请把奇数放在数组左边，偶数放在数组右边，要求所有奇数之间原始次序不变，所有偶数之间原始次序不变。要求时间复杂度O(N),额为空间复杂度O(1)。这是个01标准的partion，奇偶规则，但是快速排序的partion过程做不到稳定性。所以正常实现不了，学术论文(01 stable sort,不建议碰，比较难)中需要把数据阉割限制之后才能做到

## 1.6 工程上对排序的改进

> 稳定性考虑：值传递，直接快排，引用传递，归并排序

> 充分利用O(NlogN)和O(N^2)排序各自的优势：根据样本量底层基于多种排序实现，比如样本量比较小直接选择插入排序。

> 比如Java中系统实现的快速排序