# go_arithmetic

**Repository Path**: lihaowen2017/go_arithmetic

## Basic Information

- **Project Name**: go_arithmetic
- **Description**: 1. 链表，栈，队列，循环队列等数据结构的Go语言实现
2. Go实现常用排序算法(13种)，希尔排序，堆排序，快速排序，鸡尾酒排序等
3. 利用CSDN账号大数据测试排序算法性能

- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-02-29
- **Last Updated**: 2021-11-02

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## Go数据结构与算法

### 摘要

> 链表，栈，队列，循环队列等数据结构的Go语言实现
>
> 常用排序算法(13种)，希尔排序，堆排序，快速排序，鸡尾酒排序等
>
> 利用CSDN账号大数据测试排序算法性能

### 数组

#### 概念

> 数组的内存排列在一起
>
> 查找效率: 1次
>
> 删除一个: n次 (最坏情况)
>
> 插入: n次 (最坏情况)

##### 数组实现数组迭代器

> 定义指针能顺序遍历数据



##### 文件夹遍历

> 使用栈遍历(递归) : 深度遍历
>
> 使用队列: 广度遍历



##### 队列与循环队列

> 队列先进先出，一个尾指针表示队列现在的大小
>
> 循环队列，一个首指针，一个尾指针，首尾指针间隔为1表示队列满了，首尾指针循环过队列长度时进行取余运算回复为正数
>
> 首指针追上尾指针说明队列为空
>
> 尾指针追上首指针(间隔为1)说明队列满



##### 数组存储的方式

##### 内存连续存储

> N个元素，修改查找O(1)
>
> 删除，插入N, O(N) 最坏情况
>
> 查找修改效率高，删除插入最坏情况效率低
>
> 计算机理论上不存在大片连续内存

##### 链式存储

> 链表
>
> 删除，插入O(1)
>
> 查找，修改O(n)

##### 链式栈和队列的应用场景

> 无限扩容，类似12306订单

### 细节知识点

二叉树的根节点下标为n

左孩子节点下标为2n+1 ，右孩子节点下标为2n+2

逻辑结构:二叉树

存储结构:数组

n个节点的完全二叉树的深度为(log2n)+1

### 排序和查找

##### 选择排序

```go
func SelectSort(arr[] int) []int{
	length := len(arr) // 数组长度
	if length <= 1{
		return arr // 一个元素的数组,直接返回
	}else {
        // i 是无序区首位元素
		for i := 0; i < (length - 1); i += 1 {
			// 只剩一个元素不需要挑选
			max := i // 标记索引
			for j := i + 1; j < length; j += 1{
				// 每次选出一个极大值
				if arr[max] < arr[j]{
					max = j //保存极大值的索引
				}
			}
			if i != max {
				arr[i], arr[max] = arr[max], arr[i]
			}
		}
		return arr
	}
}
```

> 1. 数组长度小于等于1返回数组
> 2. 遍历数组长度减1次
> 3. 定义无序区首位元素下标为最小或最大
> 4. 遍历无序区迭代出最小或最大的元素
> 5. 无序区首位元素与最小或最大的元素交换，有序区往后移动一位

##### 插入排序

```go
func InsertSortLeft(arr []int) []int {
	length := len(arr) // 数组长度
	if length <= 1{
		return arr // 一个元素的数组，直接返回
	}else{
		for i:=1; i < length; i++{ // 跳过第一个
			backup := arr[i]  // 备份插入的数据
			j := i-1 // 上一个位置循环找到位置插入
			for j >= 0 && backup < arr[j] {
				arr[j+1] = arr[j] // 从前往后移动
				j--
			}
			arr[j+1] = backup
			fmt.Println(arr)
		}
		return arr
	}

}

func InsertSortRight(arr []int) []int {
	length := len(arr)
	if length <= 1{
		return arr
	}else {
		for i:=length-2;i>=0;i--{
			backup :=arr[i]
			j := i+1
			for j<=length-1&&backup<arr[j]{
				arr[j-1] = arr[j]
				j +=1
			}
			arr[j-1] = backup
			fmt.Println(arr)
		}
		return arr
	}
}
```

> 从左至右插入，从小至大
>
> 1. 从第二个数据开始一次备份遍历
> 2. 备份数据的左侧与备份数据依次比较，小于备份数据依次向右移动直至找到大于备份数据的数，插入在它的右边。未找到大于备份数据的数，将备份数据插入至最左侧

##### 冒泡排序

```go
func BubbleSort(arr []int) []int {
	length := len(arr) // 求数组长度
	if length <= 1{
		return arr
	}else {
		for i:=0;i<length-1;i+=1{ // 只剩一个不需要冒泡了
			isNeedExchange := false // 没有冒泡时直接说明排序完成进行返回
			for j:=0; j<length-1-i;j+=1{
				if arr[j] > arr[j+1]{ // 两两比较
					arr[j], arr[j+1] = arr[j+1], arr[j]
					isNeedExchange = true
				}
			}
			if !isNeedExchange {
				return arr
			}
			fmt.Println(i,arr)
		}
		return arr
	}
}
```

> 无序区初始为整个数组长度，有序区为0
>
> 从左至右，由小至大进行排序
>
> 无序区数组从最左侧开始进行两两比较，左侧大于右侧，交换两个数位置，直至遍历至无序区末尾。
>
> 有序区长度加1，无序区长度减1
>
> 优化:
>
> 当某一次无序遍历未发生位置交换情况，证明数组已有序可以退出排序。

##### 推排序

```go
func HeapSortMax(arr []int, length int) []int{
	//length := len(arr) // 数组长度
	if length <=1{
		return arr // 一个元素的数组，直接返回
	}else{
        root := length/2 -1 // 度不为0的叶子节点

		for i:=root; i>=0; i-=1 {
			// 循环所有的三节点
			topmax := i // 假定最大的在i的位置
			leftchild := 2*i+1
			rightchild := 2*i+2 // 左右孩子的节点
			if leftchild<=length-1 && arr[leftchild] > arr[topmax] {
				// 防止数组越界
				topmax = leftchild // 如果左边比我大，记录最大
			}
			if rightchild<=length-1 && arr[rightchild]>arr[topmax]{
				topmax = rightchild // 如果右边比我大，记录最大
			}
			if topmax != i {
				arr[i], arr[topmax] = arr[topmax], arr[i]
			}
		}
		return arr
	}
}

func HeapSort(arr []int) []int {
	length := len(arr)
	for i:= 0; i<length; i+=1{
		lastMessLen := length-i // 每次截取一段
		HeapSortMax(arr, lastMessLen)
		fmt.Println(arr)
		if i < length{
			arr[0], arr[lastMessLen-1] = arr[lastMessLen-1],arr[0]
			// 每次将登顶的数放到数组尾端
		}
		fmt.Println("ex",arr)
	}
	return arr
}
```

> 父节点 i; 左孩子节点为2i+1; 右孩子节点为2i+2 
>
> 计算有n个三节点(length / 2 -1) 
>
> 遍历n次逐次将三节点中最大数放置父节点的位置。
>
> 一次循环最终选出数组中最大的数
>
> 循环数组长度次数
>
> 将最大的数放置数组尾端，重新选出长度减一数组中最大的数以此类推，直至排序完成

##### 快速排序

```go
func QuickSort(arr []int) []int {
	length := len(arr) // 数组长度
	if length <= 1 {
		return arr // 一个元素的数组, 直接返回
	}else {
		n := rand.Int()%length // n>=0 && n<length-1,随机生成一个在length范围内的随机数
		splitdata := arr[n] // 以第一个为基准
		low := make([]int, 0, 0) // 存储比我小的
		high := make([]int, 0, 0) // 存储比我大的
		mid := make([]int, 0, 0) // 存储与我相等的
		mid = append(mid, splitdata) // 加入第一个相等的
		for i:=0; i < length; i+=1{
			if i == n{
				continue
			}
			if arr[i] < splitdata{
				low = append(low, arr[i])
			}else if arr[i] > splitdata{
				high = append(high, arr[i])
			}else{
				mid = append(mid, arr[i])
			}
		}
		low, high=QuickSort(low),QuickSort(high) // 切割递归处理
		myarr := append(append(low,mid...),high...)
		return myarr
	}
}
```

> 将数组分为三段，小于当前位置的，等于当前位置的，大于当前位置的。
>
> 当单侧数据只有1位的时候认为数据左中右三部分有序，此时拼接三部分(递归终止条件)

##### 奇偶排序

```go
func OddEven(arr []int) []int {
	isSorted := false // 奇数位，偶数位都不需要排序，即为有序
	for ;isSorted == false;{
		isSorted = true
		for i:=1;i<len(arr)-1;i=i+2{
			// 奇数位
			if arr[i] > arr[i+1]{
				// 需要交换，换
				arr[i],arr[i+1]=arr[i+1],arr[i]
				isSorted = false
			}
		}
		fmt.Println("奇数",arr)
		for i:=0;i<len(arr)-1;i=i+2{
			// 偶数位
			if arr[i] > arr[i+1]{
				// 需要交换，换
				arr[i],arr[i+1]=arr[i+1],arr[i]
				isSorted = false
			}
		}
		fmt.Println("偶数",arr)
	}
	return arr
}
```

> 奇偶排序使用场合，方差小的数据
>
> 所有的奇数位于身后相邻的偶数位比较交换
>
> 所有的偶数位于身后相邻的奇数位比较交换
>
> 交替循环直至两次遍历都未发生交换，排序退出返回结果

##### 归并排序及其优化

```go
func InsertSortLeft(arr []int) []int {
	length := len(arr) // 数组长度
	if length <= 1{
		return arr // 一个元素的数组，直接返回
	}else{
		for i:=1; i < length; i++{ // 跳过第一个
			backup := arr[i]  // 备份插入的数据
			j := i-1 // 上一个位置循环找到位置插入
			for j >= 0 && backup < arr[j] {
				arr[j+1] = arr[j] // 从前往后移动
				j--
			}
			arr[j+1] = backup

		}
		return arr
	}
}

func Merge(leftArr []int, rightArr []int) []int  {
	leftIndex := 0 // 左边索引
	rightIndex := 0 // 右边索引
	lastArr := []int{} // 最终的数组
	for leftIndex<len(leftArr) && rightIndex<len(rightArr) {
		if leftArr[leftIndex] < rightArr[rightIndex]{
			lastArr = append(lastArr,leftArr[leftIndex])
			leftIndex += 1
		} else if leftArr[leftIndex] > rightArr[rightIndex]{
			lastArr = append(lastArr,rightArr[rightIndex])
			rightIndex += 1
		} else{
			lastArr = append(append(lastArr,rightArr[rightIndex]),leftArr[leftIndex])
			leftIndex += 1
			rightIndex += 1
		}
	}
	for leftIndex < len(leftArr) { // 把没有结束的归并过来
		lastArr = append(lastArr,leftArr[leftIndex])
		leftIndex += 1
	}

	for rightIndex < len(rightArr) { // 把没有结束的归并过来
		lastArr = append(lastArr,rightArr[rightIndex])
		rightIndex += 1
	}
	return lastArr
}

func MergeSort(arr []int) []int {
	length := len(arr)
	if length <= 1{  // 小于10 的时候可以使用其他排序算法进行排序
		return arr
	}else if length > 1 && length < 5{
		return InsertSortLeft(arr)
	} else {
		mid := length/2
		leftArr := MergeSort(arr[:mid])
		rightArr := MergeSort(arr[mid:])
		return Merge(leftArr, rightArr)
	}
}
```

> 归并排序思想:
>
> 递归将数组进行分段，将不同分段的数组进行排序(或者分段长度为1)
>
> 将切分后的左右有序数组两两比较取出最小的放入到临时数组。
>
> 优化：切分数组时可以不切分到1而是可以在小于一定长度时使用其它排序算法进行排序。

##### 希尔排序

```go
func ShellSortStep(arr []int, start int, gap int)  {
	// 步长收缩
	length := len(arr) // 数组长度
	for i:=start+gap;i<length; i+=gap{
		backup := arr[i]  // 备份插入数据
		j := i-gap // 上一个位置循环找到位置插入
		for j>=0 &&backup<arr[j] {
			arr[j+gap] =arr[j] // 从前往后移动
			j-=gap
		}
		arr[j+gap] = backup
		fmt.Println(arr)
	}
}

func ShellSort(arr []int) []int{
	length := len(arr) // 数组长度
	if length <= 1{
		return arr //一个元素的数组，直接返回
	}else {
		gap := length/2 //步长
		for gap > 0{
			for i:=0; i<gap; i+=1 { // 处理每个元素的步长
				ShellSortStep(arr, i, gap)
			}
			gap /= 2 // gap --
		}
	}
	return arr
}
```

> 希尔排序
>
> 步长缩进的插入排序
>
> 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
>
> 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序
>
> 设定初始步长为length/2，对步长长度的数组逐次进行插入排序，直至步长为1

##### 基数排序

```go
func SelectSortMax(arr []int) int {
	// 选出一个极大值
	length := len(arr) // 数组长度
	if length <= 1 {
		return arr[0] // 一个元素的数组,直接返回
	}else {
		max := arr[0]
		for i := 1; i < length; i++ {
			if arr[i] > max {  // 任何一个比我max大的数，替换max
				max = arr[i]
			}
		}
		return max
	}
}

func BucketSort(arr []int) []int {
	max := SelectSortMax(arr)  // 寻找数组的极大值
	for bit:=1; max/bit>0;bit*=10{
		// 按照数量级分段
		arr = BitSort(arr, bit) // 每次处理一个级别的排序
		fmt.Println(arr)
	}
	return arr
}

func BitSort(arr []int, bit int) []int {
	// 处理1位，10位，100位... 的每组的排序
	length := len(arr) // 数组长度
	bitCounts := make([]int, 10) // 统计长度0, 1, 2, 3, 4, 5, 6, ...,9(余数区间)
	for i:=0;i<length;i+=1{
		num := (arr[i]/bit) % 10 // 分层处理, bit=1000, 三位数不参与排序 1/10 = 0; 0%10 = 0
		bitCounts[num] += 1 // 统计分段中余数相等个数,随着位数增大余数为0的段不断增加
	}
	fmt.Println(bitCounts)
	// 0, 1, 2, 3, 4, 5 余数
	// 1, 0, 3, 0, 0, 1 余数个数
	// 1, 1, 4, 4, 4, 5 累加，计算位置的分布
	for i:=1; i<10;i+=1{
		bitCounts[i] += bitCounts[i-1] // 叠加, 计算位置分布，随着位数增大余数为0的段不断增加
	}
	fmt.Println(bitCounts)
	tmp := make([]int, 20)  // 开辟临时数组
	fmt.Println("bit",bit)
	for i:=length-1;i>=0;i-=1{
		// 关键点倒序，由低位往高位逐次遍历，由余数大的往余数小的遍历
		num:=(arr[i]/bit) % 10
		fmt.Println("num",num)
		tmp[bitCounts[num]-1] =arr[i]  // 计算排序的位置
		bitCounts[num] -=1
		fmt.Println("tmp",tmp)
	}

	for i:=0;i<length;i+=1 {
		arr[i] = tmp[i]
	}
	return arr
}
```

> 基数排序，采取的是分治思想，以余数(0-9)为桶
>
> 将数据以位数进行分层，将余数相同的放到一个桶内，个位，十位，百位以此类推，也就是先是判断个位放到0-9的桶内，再是判断十位放到0-9桶内以此类推，位数往后推一位则不满足该位数的数据不参与排序(余数为0了)，以此类推最终使数组有序

##### 计数排序

```go
func SelectSortMax(arr []int) int {
	// 选出一个极大值
	length := len(arr) // 数组长度
	if length <= 1 {
		return arr[0] // 一个元素的数组,直接返回
	}else {
		max := arr[0]
		for i := 1; i < length; i++ {
			if arr[i] > max {  // 任何一个比我max大的数，替换max
				max = arr[i]
			}
		}
		return max
	}
}

func Countsort(arr []int) []int {
	max := SelectSortMax(arr) // 寻找最大值
	sortedarr := make([]int, len(arr)) // 排序之后存储
	countsarr := make([]int, len(arr)) // 统计次数
	//fmt.Println(len(arr))
	for _, v := range arr {
		countsarr[v]++
	}
	fmt.Println("第一次统计次数", countsarr) // 统计次数

	for i:=1; i<=max; i+=1{
		countsarr[i]+=countsarr[i-1] // 叠加
	}
	fmt.Println("次数叠加", countsarr) // 统计次数
	for _, v := range arr {
		sortedarr [countsarr[v]-1] = v // 展开数据
		countsarr[v] -= 1 // 递减
		fmt.Println("zkcount", countsarr)
		fmt.Println("zk", sortedarr)
	}
	return sortedarr
}
```

```go
func Countsort(arr []int) []int {
	max := SelectSortMax(arr) // 寻找最大值
	countsarr := make([]int, max+1) // 统计次数
	for _, v := range arr {
		countsarr[v]++
	}
	fmt.Println("第一次统计次数", countsarr) // 统计次数,下标为数值，值为下标数值出现的次数
	arr = make([]int, 0, 0) // 清空原数组
	for i, v := range countsarr {

		for j:=0;j<v; j+=1{
			arr = append(arr ,i)
		}
	}
	return arr
}
```

> 对列表进行排序，已知列表中数范围都在0-100之间。设计时间复杂度为O(n)的算法。
>
> 1. 获取数组最大值，建立以最大值为长度的空数组，统计数组每个数出现的个数记录到新数组中。新数组下标为原数组数值，值为数值出现次数
>
> 2. 输出新数组: 
>
>    遍历新数组，循环输出值次数的下标，追加到清空的数组

##### 鸡尾酒排序(双向冒泡)

```go

func CocktailSort(arr []int) []int {
	for i:=0; i<len(arr)/2;i+=1{
		// 每次循环，正向冒泡一次，反向冒泡一次
		left := 0
		right := len(arr)-1 // 左边，右边
		for left <= right {// 结束的条件
			if arr[left] > arr[left+1]{
				arr[left], arr[left+1] = arr[left+1], arr[left]
			}
			left += 1
			if arr[right-1] > arr[right]{
				arr[right-1], arr[right] = arr[right], arr[right-1]
			}
			right -= 1
		}
		fmt.Println(arr)
	}
	return arr
}
```

> 鸡尾酒，双向冒泡
>
> 左侧将大数沉底至中间位置往右一位
>
> 右侧将小数浮起至中间位置往左一位
>
> 循环数组长度除以2的次数
>
> 也可以直接双向冒泡

### 数据结构

#### 数据结构分类(存储结构，逻辑结构)

> 数据结构按照其逻辑结构可分为线性结构、树结构、图结构
>
> 线性结构: 数据结构中的元素存在一对一的相互关系
>
> 树结构: 数据结构中的元素存在有一对多