排序算法总结

基础排序算法

点击查看代码

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package basic_sort

/**
 * @Author: yirufeng
 * @Date: 2021/4/13 8:28 下午
 * @Desc: 选择排序

时间复杂度：假设数组中有n个数字
	大循环需要遍历n-2趟，然后每一个大循环中，
							我们都需要从开始的数字一直到最后选出最小的数字(时间复杂度：O(n))，然后填充到当期那还没有排好序的起始位置

最后总的时间复杂度：O(n^2)，
空间复杂度：O(1)。
稳定的排序算法（因为两个相等的数字前面那个一定是排序的时候第一个会被放置到前面的）
 **/

func SelectedSort(nums []int) {
	selectedSort(nums)
}

func selectedSort(nums []int) {
	var min int
	for i := 0; i < len(nums)-1; i++ {
		//每次从nums[i]开始起
		min = i
		//依次与后面比对来选择最小的
		for j := i + 1; j < len(nums); j++ {
			if nums[min] > nums[j] {
				min = j
			}
		}
		//交换nums[min]与nums[i]
		nums[i], nums[min] = nums[min], nums[i]
	}
}

选择排序

选择排序总结：

  1. 时间复杂度：O(n^2)
  2. 空间复杂度：O(1)。
  3. 不稳定的排序算法（比如A 80 B 80 C 70 这三个卷子从小到大排序，最后将会变成CBA，但是稳定的应该是CAB）

三个版本的冒泡排序：

  1. 最基本的
  2. 如果某次冒泡的时候没有交换元素，那么说明这一趟以及后面的元素都是有序的，之后后面我们就不再需要进行冒泡，可以直接退出
  3. 在第二种改进的基础上再使用一个变量，表示我们最后交换的位置，下次遍历到这个位置就可以了

点击查看代码

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package basic_sort

/**
 * @Author: yirufeng
 * @Date: 2021/4/13 8:28 下午
 * @Desc:

有好几个版本：
1. 最基本的
2. 如果某次冒泡的时候没有交换元素，那么说明这一趟以及后面的元素都是有序的，之后后面我们就不再需要进行冒泡，可以直接退出
3. 在第二种改进的基础上再使用一个变量，表示我们最后交换的位置，下次遍历到这个位置就可以了
 **/

func BubbleSort(nums []int) {
	bubbleSortV2(nums)
}

//最基本的
func bubbleSortV1(nums []int) {
	for i := 1; i < len(nums); i++ { //冒泡的次数
		for j := 0; j < len(nums)-i; j++ {
			//如果前面比后面大就交换
			if nums[j] > nums[j+1] {
				nums[j], nums[j+1] = nums[j+1], nums[j]
			}
		}
	}
}

//如果某次冒泡的时候没有交换元素，那么说明这一趟以及后面的元素都是有序的，之后后面我们就不再需要进行冒泡，可以直接退出
func bubbleSortV2(nums []int) {
	//表示某一趟是否有元素交换
	flag := true
	for i := 1; i < len(nums); i++ { //冒泡的次数
		flag = true
		for j := 0; j < len(nums)-i; j++ {

			//如果前面比后面大就交换
			if nums[j] > nums[j+1] {
				flag, nums[j], nums[j+1] = false, nums[j+1], nums[j]
			}
		}
		//如果没有元素交换，说明已经有序，直接退出即可
		if flag {
			break
		}
	}
}

//在第二种改进的基础上再使用一个变量，表示我们最后交换的位置，下次遍历到这个位置就可以了
//使用一个变量记录最后发生交换的位置，说明该位置之后都是有序的
func bubbleSortV3(nums []int) {
	//表示某一趟是否有元素交换
	flag := true
	//表示最后发生交换的位置
	//注意点1:这里必须再额外使用临时变量，因为如果只是用一个变量lastSwapPos的话，
	//lastSwapPos的值会一直改变，因此如果一旦变小，我们的for循环就会推出
	lastSwapPos := len(nums) - 1     //注意点2：初始值赋值是len(nums) - 1
	for i := 1; i < len(nums); i++ { //冒泡的次数
		lastSwapPosTemp := len(nums) - i //注意点3：初始值赋值是len(nums) - i
		flag = true
		//下次遍历的时候遍历到我们上次最后发生交换的位置就可以了
		for j := 0; j < lastSwapPos; j++ {
			//如果前面比后面大就交换
			if nums[j] > nums[j+1] {
				flag, nums[j], nums[j+1], lastSwapPosTemp = false, nums[j+1], nums[j], j //注意点4：这里lastSwapPosTemp应该赋值j，因为j与j+1比较过了，所以就认为j之后是已经有序的了
			}
		}
		//如果没有元素交换，说明已经有序，直接退出即可
		if flag {
			break
		}

		lastSwapPos = lastSwapPosTemp
	}
}

冒泡排序

冒泡排序总结：

  1. 时间复杂度：O(n^2)，最好是O(n)
  2. 空间复杂度：O(1)。
  3. 稳定

点击查看代码

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package basic_sort

/**
 * @Author: yirufeng
 * @Date: 2021/4/13 8:28 下午
 * @Desc:

时间复杂度：O(n^2)
空间复杂度：O(1)
稳定的：因为是到前面找到一个小于等于自己的后面那个位置
 **/

func InsertSort(nums []int) {
	insertSort(nums)
}

func insertSort(nums []int) {
	var j int
	//第一个元素已经有序，只需要插入后面的元素即可
	for i := 1; i < len(nums); i++ {
		//当前要插入的元素目前位于i位置
		cur := nums[i]
		//从后往前找，直到前面元素小于当前元素就停，并且遍历的过程中不断将前面的元素移动到后面
		for j = i - 1; j >= 0 && nums[j] > cur; j-- {
			nums[j+1] = nums[j]
		}
		//此时j指向的元素就是前面那个小于或者等于当前元素的位置
		//但是我们应该在j+1位置插入
		nums[j+1] = cur
	}
}

直接插入排序总结

直接插入排序总结：

  1. 时间复杂度：O(n^2)，
  2. 空间复杂度：O(1)。
  3. 稳定的：因为是到前面找到一个小于等于自己的后面那个位置

进阶排序算法

点击查看代码

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package advanced_sort

import (
	"algos/模板/排序/util"
	"fmt"
	"sort"
)

/**
 * @Author: yirufeng
 * @Date: 2021/4/14 3:31 下午
 * @Desc: 归并排序
 **/

func MergeSort(nums []int) {
	mergeSort(nums, 0, len(nums)-1)
}

func mergeSort(nums []int, l, r int) {
	if l == r {
		return
	}

	//找到中间点，一分为二
	mid := l + (r-l)>>1
	//划分成左右两个有序的空间
	mergeSort(nums, l, mid)
	mergeSort(nums, mid+1, r)
	//将左右两部分以mid为划分轴进行合并
	merge(nums, l, mid, r)

}

//合并nums[l:mid+1] 与 nums[mid+1:r+1]两部分内容
func merge(nums []int, l, mid, r int) {
	i, j := l, mid+1
	cur := 0
	//注意点1：这里必须借助一个数组，否则我们前面可能还没有被排序的结果会被我们后半部分的内容覆盖掉，导致前面就没有内容
	help := make([]int, r-l+1)
	for i <= mid && j <= r {
		if nums[i] < nums[j] {
			help[cur], cur, i = nums[i], cur+1, i+1
		} else {
			help[cur], cur, j = nums[j], cur+1, j+1
		}
	}

	for i <= mid {
		help[cur], cur, i = nums[i], cur+1, i+1
	}
	for j <= r {
		help[cur], cur, j = nums[j], cur+1, j+1
	}

	//最后记得我们的help数组中的内容要放回到我们的原来的数组中
	for i := 0; i < len(help); i++ {
		nums[l+i] = help[i]
	}
}

func main() {
	nums := util.GenerateRandomNums(0, 100, 30)
	fmt.Println(nums)
	temp := make([]int, 30)
	copy(temp, nums)
	sort.Ints(temp)
	MergeSort(nums)
	fmt.Println(temp)
	fmt.Println(nums)
}

归并排序

  1. 时间复杂度：O(nlogN) 最好最坏都是O(NlogN)
  2. 空间复杂度：O(n)。需要一个辅助空间
  3. 是否稳定：稳定的（因为一旦两个数相等我们就不比较，并且每次都是前半部分与后半部分进行比较，所以前面同样的内容与后面同样的内容的相对位置不会改变）

点击查看代码

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
package main

import (
	"algos/模板/排序/util"
	"fmt"
	"log"
	"sort"
)

/**
 * @Author: yirufeng
 * @Date: 2021/4/14 3:29 下午
 * @Desc: 从小到大的堆排序(需要建立一个大顶堆)

从小到大排序需要建立一个大顶堆，因为我们建立好大顶堆之后，每次从堆头开始排除元素，然后都会将堆头放到目前数组的最后位置，最后位置会不断缩小，
因此我们最后的位置就是一个不断往前移动的过程，从而就是说我们得到的整个数组是从小到大的
 **/

func HeapSort(nums []int) {
	heapSort(nums)
}

func heapSort(nums []int) {
	if nums == nil || len(nums) < 2 {
		return
	}

	for i := 0; i < len(nums); i++ {
		heapPush(nums, i)
	}

	log.Println("建堆完成--------------->", nums)
	heapSize := len(nums)

	//之后不断吐出元素
	for heapSize > 0 {
		nums[0], nums[heapSize-1] = nums[heapSize-1], nums[0]
		heapSize--
		heapify(nums, heapSize)
	}
}

//表示当前要加入的是nums中的索引为index的元素
func heapPush(nums []int, index int) {
	for (index-1)>>1 >= 0 && nums[index] > nums[(index-1)>>1] {
		nums[index], nums[(index-1)>>1], index = nums[(index-1)>>1], nums[index], (index-1)>>1
	}
}

//length 表示堆的元素个数
func heapify(nums []int, length int) {
	index := 0
	// (index << 1 + 1) < length 说明是有左子树的
	for (index<<1 + 1) < length { //思路：每次找到左右孩子中更大的与父进行交换
		left := index<<1 + 1
		//如果有右子树并且右子树比左子树大
		if left+1 < length && nums[left+1] > nums[left] {
			left++
		}
		//如果当前节点比左右孩子中大的大，就不交换
		if nums[left] <= nums[index] {
			break
		}
		//如果当前节点比左右孩子中大的小，交换当前节点与左右孩子中较大的
		//同时让index变为left
		nums[left], nums[index], index = nums[index], nums[left], left
	}
}

func main() {
	nums := util.GenerateRandomNums(0, 100, 50)
	temp := make([]int, 50)
	copy(temp, nums)
	sort.Ints(temp)
	fmt.Println(temp)
	HeapSort(nums)
	fmt.Println(nums)
}

点击查看代码

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
package main

import (
	"algos/模板/排序/util"
	"fmt"
	"sort"
)

/**
 * @Author: yirufeng
 * @Date: 2021/4/15 2:20 下午
 * @Desc: 从大到小的排序，需要建立一个小顶堆
 **/

func HeapSort(nums []int) {
	heapSort(nums)
}

func heapSort(nums []int) {

	//如果nums为空或者元素个数小于两个，可以直接退出
	if nums == nil || len(nums) < 2 {
		return
	}

	//此时我们需要不断将元素加入我们的堆中
	for i := 1; i < len(nums); i++ {
		heapInsert(nums, i)
	}

	//获取堆的大小
	heapSize := len(nums)

	//此时我们不断将堆里面的元素弹出放到应该放置的位置
	for heapSize > 0 {
		//将堆的最后一个元素与堆顶交换
		nums[0], nums[heapSize-1] = nums[heapSize-1], nums[0]
		//堆的元素个数减去1
		heapSize--
		//开始从堆顶从上往下开始调整堆
		heapAdjustFromTopToBottom(nums, heapSize-1) // 从下到上的堆调整
	}
}

//第二个参数表示插入的元素位于nums的位置
func heapInsert(nums []int, index int) {
	//不断比较当前插入的位置的元素与父节点的大小，如果比父节点小就交换
	for (index-1)>>1 >= 0 && nums[(index-1)>>1] > nums[index] {
		nums[index], nums[(index-1)>>1], index = nums[(index-1)>>1], nums[index], (index-1)>>1
	}
}

//第二个参数表示当前堆的元素个数
func heapAdjustFromTopToBottom(nums []int, length int) {
	index := 0
	for index<<1+1 < length {
		left := index<<1 + 1

		//如果有右孩子并且右比左小
		if left+1 < length && nums[left+1] < nums[left] {
			left++
		}

		//当前节点小于等于两个孩子较小的
		if nums[index] <= nums[left] {
			break
		}
		nums[index], nums[left], index = nums[left], nums[index], left
	}
}

func main() {
	nums := util.GenerateRandomNums(0, 100, 50)
	temp := make([]int, 50)
	copy(temp, nums)
	sort.Ints(temp)
	fmt.Println(temp)
	HeapSort(nums)
	fmt.Println(nums)
}

点击查看代码

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package main

import (
	"algos/模板/排序/util"
	"fmt"
	"math/rand"
	"sort"
)

/**
 * @Author: yirufeng
 * @Date: 2021/4/14 3:31 下午
 * @Desc: 从小到大的快速排序
 **/

func QuickSort(nums []int) {
	quickSort(nums, 0, len(nums)-1)
}

//表示对[l,r]的元素进行快排
func quickSort(nums []int, l, r int) {
	if l < r {
		//在[l,r]区间内生成一个随机数作为划分
		index := rand.Intn(r-l+1) + l
		//每次都把我们随机选择的元素交换到最后
		nums[index], nums[r] = nums[r], nums[index]
		//进行划分，得到两个相等的区间
		less, more := partition(nums, l, r)
		//继续对小于和大于的两个区间进行快速排序
		quickSort(nums, l, less-1)
		quickSort(nums, more+1, r)
	}
}

//返回两个结果是等于我们随机数的区间的左端点和右端点
func partition(nums []int, l, r int) (int, int) { //使用nums[r]作为一个划分
	less, more := l-1, r
	num := nums[r]
	cur := l
	for cur < more {
		if nums[cur] < num {
			nums[less+1], nums[cur], less, cur = nums[cur], nums[less+1], less+1, cur+1
		} else if nums[cur] > num {
			nums[more-1], nums[cur], more = nums[less+1], nums[more-1], more-1
		} else if nums[cur] == num {
			more++
		}
	}
	nums[more], nums[r] = nums[r], nums[more]
	//每次随机择一个划分点
	return less + 1, more - 1
}

func main() {
	nums := util.GenerateRandomNums(0, 100, 10)
	fmt.Println(nums)
	temp := make([]int, 10)
	copy(temp, nums)
	sort.Ints(temp)
	fmt.Println(temp)
	QuickSort(nums)
	fmt.Println(nums)
}

快速排序

思路：采用荷兰国旗的问题进行划分，每次可以划分为3个区间，分别是小于，等于以及大于的区间。

  1. 时间复杂度：O(nlogN) 最好是O(nlogN) 最坏是O(n^2)
  2. 空间复杂度：O(n)。
  3. 是否稳定：不稳定

！！！

算法排序

二叉树，二叉搜索树，AVL树，B树，B+树

二叉树树形结构，但是树中每个节点的分支最多只有两个，我们叫做二叉树 二叉搜索树(BST)!> 二叉搜索树又叫二叉排序树，或二叉查找树。它或者是一颗空树或者是具有下列性质的二叉树： 若它的左子树不为空，则左子树上的所有节点的值均小于它的根节点的值 若它的右子树不为空，则右子树上的所有节点的值均大于它的根节点的值 它的左右子树也分别是二叉排序树 平衡二叉树(AVL)!> 平衡二叉...
算法树

(LeetCode系列)寻找旋转排序数组中的值

前言

在旋转数据中搜索值包括两个系列的题型：搜索旋转点(也就是最小值)以及搜索我们给定的目标值。关于旋转排序数组的定义这里就不再赘述

算法二分

(LeetCode系列)矩阵中的搜索

套路总结

套路总结

sCRjwC

注意：方法一二代码较为简单，这里就不再赘述了

方法三

上图中的方法三，我们以LeetCode 240为例

代码

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/** ✅
 * @Author: yirufeng
 * @Date: 2020/12/7 11:41 上午
 * @Desc:
 * 方法一：暴力
 * 方法二：从右上角或者左下角每次排除一行或者一列
 * 方法三：每一行二分搜索
 * 方法四：采用二分
		思路：获取当前搜索矩阵的中心点，然后排出左上角或者右下角的矩阵
	如下是方法四代码
 **/
func searchTarget(matrix [][]int, x1, y1, x2, y2, target int) bool {
	//递归可能越界
	if x1 > x2 || y1 > y2 {
		return false
	}

	//之前这个if语句块没有写会死循环，
	//注意点：避免x1，y1，x2，y2相等时调用searchTarget(matrix, x1, y1, xMid, yMid, target)死循环
	if x1 == x2 && y1 == y2 {
		if matrix[x1][y1] == target {
			return true
		}
		return false
	}

	//得到中心点坐标
	xMid, yMid := x1+(x2-x1)>>1, y1+(y2-y1)>>1
	if matrix[xMid][yMid] > target { //排除右下角
		return searchTarget(matrix, x1, y1, xMid, yMid, target) ||
			searchTarget(matrix, x1, yMid+1, xMid-1, y2, target) ||
			searchTarget(matrix, xMid+1, y1, x2, yMid-1, target)
	} else if matrix[xMid][yMid] < target { //排除左上角
		return searchTarget(matrix, x1, yMid+1, xMid, y2, target) ||
			searchTarget(matrix, xMid+1, y1, x2, yMid, target) ||
			searchTarget(matrix, xMid+1, yMid+1, x2, y2, target)
	}
	return true

}

func searchMatrix(matrix [][]int, target int) bool {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return false
	}
	return searchTarget(matrix, 0, 0, len(matrix)-1, len(matrix[0])-1, target)
}

算法二分

二叉树的序列化与反序列化

前言

序列化：二叉树被记录成文件的过程叫做序列化

反序列化：通过文件内容重建原来二叉树的过程叫做反序列化

二叉树的三种遍历方式

基于递归的遍历

算法面试

树形DP套路

步骤

  1. 以某个节点X为头结点的子树中，分析答案有哪些可能性，并且这种分析是以X的左子树，X的右子树，和X整棵树的角度来考虑可能性的
  2. 根据第一步分析的可能性，列出所需要的信息，例如在二叉树是否平衡中，左子树和右子树都需要知道各自是否平衡，以及高度这两个信息。
  3. 根据第二步信息汇总，定义自己的信息结构体
  4. 设计递归函数，递归函数是处理以X为头结点的情况相爱的答案，包括设计递归函数的base case，默认直接得到左树和右树所有的信息，以及把可能性左整合，并且返回第三步的信息结构这4个小步骤。
算法面试

布隆过滤器总结

了解布隆过滤器

什么是布隆过滤器？

一个布隆过滤器精确地代表了一个集合。并不像哈希表那样存储原始信息，而是存储原始信息的压缩信息以节省空间，但牺牲了一定的准确度。

布隆过滤器的作用

可以精确地判断一个元素是否在这个集合中。注意只是精确代表和精确判断，到底有多精确，取决于我们自己的设计。想做到完全正确是不可能的，布隆过滤器的优势在于使用很少的空间就可以将准确率做到很高的程度。

算法面试

BFPRT算法-Golang

这个BFPRT算法找逻辑Bug找了两天

注意点：

  1. 在找中位数的时候对传入的数组进行排序，这里使用直接插入排序，因为元素个数最多为5，插排常数项极低
    1. 注意：这里不是nums[j] > nums[i]而是for j = i - 1; j >= start && nums[j] > temp; j--，因为后面会对nums[i]造成修改
  2. 找中位数数组的中位数medianOfMedians返回的是最终的中位数的值，我们使用这个值进行Partition，自己这里还一直将其当做返回的索引用，导致越界
  3. BFPRT函数调用自己的时候，参数一定要对应，自己在写的时候直接将k传入了start
算法BFPRT

固定长度的数组实现栈

题目描述

使用一个固定长度大小的数组实现栈

思路

思路：使用一个index进行指向当前可以插入元素的位置
  1. 使用一个index指向下次栈中加入元素的位置
  2. 如果要弹出元素，需要判断index是否大于1，如果大于弹出index-1位置的元素，index减去1，否则不可以弹出。
  3. 如果要加入元素，直接加入到index指向的位置，之后index++
算法数据结构

1 / 3