排序算法总结

基础排序算法

点击查看代码

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. 是否稳定:不稳定

!!!

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

前言

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

两个全排列的题目

第一道题

ZWdEW0

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

前言

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

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

Golang中刷题关于切片的一些坑

问题1

问题描述:递归的过程中,传递了一个切片作为参数,每次我们都需要对切片切取首元素,之后递归回来的时候发现切片中的元素还是没有切取首元素,是一个很严重的逻辑错误

问题解决:我们递归函数使用切片作为参数的时候,我们直接传入切片的地址。因为切片每次删除元素,地址也会改变。当切片增加元素引起扩容,地址也会发生改变,而如果只传入切片我们只是引用最开始的时候的切片的地址,因此会发现切片没有任何改变。

例如我们自己写的二叉树序列化和反序列化代码:在最开始只是传递一个切片,但是后来传递切片的地址进去发现代码逻辑正常运行。

代码

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
//方法一:使用先序遍历进行序列化和反序列化
//进行序列化
func PreorderSerialize(root *TreeNode) string {
if root == nil {
return "#!"
}

var ret string

ret += strconv.Itoa(root.Val) + "!"
ret += PreorderSerialize(root.Left)
ret += PreorderSerialize(root.Right)
return ret
}

//进行反序列化
func PreorderDeserialize(ret string) *TreeNode {
strs := strings.Split(ret, "!")

//注意点:由于切片在执行过程中有可能会因为增加和删除元素而造成切片不是原来那个切片,但是我们递归回去的时候还是指向原来的切片,因此会有问题
//所以这里我们传递的是切片的地址
//因为切片扩容可能会生成一个新的底层数组,并且由于切片移除了元素,因此对应的头部地址一定会改变,所以会造成地址的改变
root := ReconstructTreeFromPreorder(&strs)
return root
}

//根据我们分割后的字符串建立二叉树
func ReconstructTreeFromPreorder(strs *[]string) *TreeNode {
if (*strs)[0] == "#" {
(*strs) = (*strs)[1:]
return nil
}

//首先将该值对应的字符串转换为int
val, _ := strconv.Atoi((*strs)[0])
//建立一个针对于该值的节点
node := &TreeNode{
Val: val,
}

//去掉我们建立过的节点的值
(*strs) = (*strs)[1:]
//之后进行递归建立左右子树
node.Left = ReconstructTreeFromPreorder(strs)
node.Right = ReconstructTreeFromPreorder(strs)

return node
}

布隆过滤器总结

了解布隆过滤器

什么是布隆过滤器?

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

布隆过滤器的作用

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

固定长度的数组实现栈

题目描述

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

思路

思路:使用一个index进行指向当前可以插入元素的位置

  1. 使用一个index指向下次栈中加入元素的位置
  2. 如果要弹出元素,需要判断index是否大于1,如果大于弹出index-1位置的元素,index减去1,否则不可以弹出。
  3. 如果要加入元素,直接加入到index指向的位置,之后index++

固定长度的数组实现队列

题目描述

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

思路

思路:使用start指向队头,end指向队尾的下一个位置

  1. 我们加了一个标志位empty区分start等于end的两种情况,一种是队列中没有元素,另外一种是队列元素满。
  2. 如果要弹出元素,需要判断end是否等于start,如果empty为真且start等于end,说明不可以弹出,否则可以弹出元素。
  3. 如果要加入元素,直接加入到end指向的位置,之后end需要判断是否处于最后一个位置,如果是则跳转到数组第1个位置,否则end++。同时判断是否满元素来更新empty

不基于比较的排序找到数组排序后的最大差值

题目描述

给定一个数组,求如果排序之后,相邻两数的最大差值,要求时 间复杂度O(N),且要求不能用非基于比较的排序

注意不基于比较哦

思路

思路:桶排序

  1. 假设数组长度为n,准备n+1个桶
  2. 遍历该数组,将最小值放入到第1个位置,将最大值放入到最后一个位置
  3. 将剩下的数等分成等分成n-1份依次放入剩下对应范围的桶中,
  4. 最后这n+1个桶中至少有一个空桶,说明桶内的数值差不是最大差值,我们去桶间找最大差值
  5. 对于每个桶,我们都保存了每个桶的最小值和最大值,从第2个桶开始,每次计算当前桶的最小值与前一个桶(要有元素)的最大值的差,过程中我们动态更新最大差值

堆排序

堆排序基本知识

基本介绍

堆是一个完全二叉树,因此我们可以利用节点的特性去使用一个数组模拟一颗完全二叉树:

  1. 下标为i的节点的左子节点的下标为i*2+1, 右子节点的下标为i*2+2
  2. 下标为i的节点的父节点的下标为(i-1)/2

建立堆的时间复杂度:O(log1) + O(log2) + … + O(logN) 近似于 O(N),因此建立堆的时间复杂度为O(N)

堆有大根堆以及小根堆,没有规定堆中左子树的根必须大于(或小于)右子树的根。

堆排序的两个基本步骤:(具体说明看代码注释)

  1. 建堆,循环将数组中的每个数加入堆中(每次都需要heapInsert)
  2. 不断从堆的最后一个元素交换到堆的头部,然后将堆的长度减小1,再调整堆,每次都需要heapify