8000 feat(algorithm): add bubble sort · shgopher/408@31b1ce6 · GitHub
[go: up one dir, main page]
Skip to content

Commit 31b1ce6

Browse files
shgophershgopher
committed
feat(algorithm): add bubble sort
1 parent 31e2406 commit 31b1ce6

File tree

13 files changed

+331
-18
lines changed

13 files changed

+331
-18
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -46,6 +46,7 @@ hey~，我是科科人神，目前就职于国内一家互联网公司，你们
4646
- [舞蹈链](/算法/数据结构/舞蹈链/README.md)
4747
- [森林](/算法/数据结构/森林/README.md)
4848
### 算法
49+
- [大 o 法表示算法效率](/算法/算法/o/README.md)
4950
- [dp](/算法/算法/dp/README.md)
5051
- [贪心](/算法/算法/贪心/README.md)
5152
- [分治](/算法/算法/分治/README.md)

‎算法/算法/README.md

Lines changed: 29 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -1,23 +1,34 @@
1+
<!--
2+
* @Author: shgopher shgopher@gmail.com
3+
* @Date: 2022-05-24 23:42:43
4+
* @LastEditors: shgopher shgopher@gmail.com
5+
* @LastEditTime: 2023-01-11 23:33:11
6+
* @FilePath: /408/算法/算法/README.md
7+
* @Description: 算法
8+
*
9+
* Copyright (c) 2023 by shgopher shgopher@gmail.com, All Rights Reserved.
10+
-->
111

212
# 算法
3-
- [dp](./算法/dp/README.md)
4-
- [贪心](./算法/贪心/README.md)
5-
- [分治](./算法/分治/README.md)
6-
- [回溯](./算法/回溯/README.md)
7-
- [dfs](./算法/dfs/README.md)
8-
- [bfs](./算法/bfs/README.md)
9-
- [排序算法](./算法/排序算法/README.md)
10-
- [二分法](./算法/二分法/README.md)
11-
- [拓跋排序](./算法/拓跋排序/README.md)
12-
- [最短路径](./算法/最短路径/README.md)
13-
- [短地址生成算法](./算法/短地址生成算法/README.md)
14-
- [字符串匹配算法](./算法/字符串匹配算法/README.md)
15-
- [限流算法](./算法/限流算法/README.md)
16-
- [唯一id生成算法](./算法/唯一id生成算法/README.md)
17-
- [抢红包算法](./算法/抢红包算法/README.md)
18-
- [topk](./算法/topk/README.md)
19-
- [洗牌算法](./算法/洗牌算法/README.md)
20-
- [限流算法](./算法/限流算法/README.md)
13+
14+
- [dp](./dp/README.md)
15+
- [贪心](./贪心/README.md)
16+
- [分治](./分治/README.md)
17+
- [回溯](./回溯/README.md)
18+
- [dfs](./dfs/README.md)
19+
- [bfs](./bfs/README.md)
20+
- [排序算法](./排序算法/README.md)
21+
- [二分法](./二分法/README.md)
22+
- [拓跋排序](./拓跋排序/README.md)
23+
- [最短路径](./最短路径/README.md)
24+
- [短地址生成算法](./短地址生成算法/README.md)
25+
- [字符串匹配算法](./字符串匹配算法/README.md)
26+
- [限流算法](./限流算法/README.md)
27+
- [唯一id生成算法](./唯一id生成算法/README.md)
28+
- [抢红包算法](./抢红包算法/README.md)
29+
- [topk](./topk/README.md)
30+
- [洗牌算法](./洗牌算法/README.md)
31+
- [限流算法](./限流算法/README.md)
2132

2233
## 参考资料：
2334
- https://zhuanlan.zhihu.com/p/349940945

‎算法/算法/o/README.md

Lines changed: 204 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,204 @@
1+
<!--
2+
* @Author: shgopher shgopher@gmail.com
3+
* @Date: 2023-01-10 23:44:05
4+
* @LastEditors: shgopher shgopher@gmail.com
5+
* @LastEditTime: 2023-01-12 19:50:15
6+
* @FilePath: /408/算法/算法/o/README.md
7+
* @Descriptipi
8+
* 使用大 o 的方式去评价算法的效率
9+
* Copyright (c) 2023 by shgopher shgopher@gmail.com, All Rights Reserved.
10+
-->
11+
# 大 o 法评价算法效率
12+
13+
在大o法去评价一个算法的效率时，我们一定要假设n时无穷大，因为我们有的时候会发现，不同的数量级，同样两个算法的对比将产生不同的效果，但是凡事总有一个标准，当我们评价算法，使用大o法去测试算法时，n 就是无穷大，因为计算机中的数量远超人类的想象，比如有些人认为1亿是一个很大的数量级，但是在计算机中这不算什么，所以鉴于人类无法想象在计算机中数量的级别，我们在测试算法时默认n就是无穷大。
14+
15+
我们使用 `T(n)` 表示数量n和时间的函数关系，`f(n)` 表示 n 数量级的数执行的次数总和，使用 `T(n) = O(f(n))` 公式，来表示代码的执行时间随着数量级的上升所呈现出的变化趋势。
16+
17+
其中 `O` 表示代码执行的时间 `T(n)` 和 执行次数`f(n)` 表达式成正比，因为在数学的体系中，o的概念就是表示：如果两个函数`f(n)` `g(n)` 在 n 趋近于无穷大的时候，比值是一个常数，那么它们就可以看成同一个数量级的函数。
18+
19+
所以大o表达法并不是真的表示具体的执行时间，而仅仅是表示一种趋势， 通常我们使用 `O(n)` 此类的简写方式来表达算法的执行效率，称之为复杂度，如果前面的是 `T(n)`就表示时间复杂度，如果前面的是表示内存的大小的，就表示是空间复杂度，
20+
21+
**总结一下，大o法表示的是随着数量的提升，消耗资源的渐进式趋势。**
22+
23+
上文说到，o并不是真的时间，而是一种趋势，我们解释一下，看一个例子：
24+
25+
```go
26+
func number(n int) {
27+
sum :=0
28+
i:= 0
29+
j:= 0
30+
31+
for ;i<n;i++ {
32+
j = 1
33+
for ;j<n;j++ {
34+
sum+= i *j
35+
}
36+
}
37+
}
38+
39+
```
40+
我们就可以推断 `T(n) = (2n^2+2n+3)*每次的时间 ` 但是其实我们并不care每次的时间是多少，那么假设我们舍弃了每次的时间这个参数，就相当于除以了这个参数，相除就是比值，得出来的数据使用 `O` 来表示的话，这个算式的结局就是 `T(n) = O(2n^2+2n+3)` 简称 `O(2n^2+2n+3)` 。
41+
42+
当n无穷大时，系数，常量，低阶都不能左右增长的趋势，那么我们完全可以省略它们，所以这个算法的最终时间随着数量的增长而存在的增长趋势 --- 时间复杂度就是`T(n) = O(n^2)`。
43+
44+
## 寻找复杂度的一些技巧
45+
1. 关注循环执行最多的一段代码,总复杂度等于量级最大的代码的复杂度
46+
2. 乘法法则，嵌套代码的复杂度等于里外之积
47+
48+
我们依然使用同样的例子去解释技巧
49+
```go
50+
sum :=0
51+
i:= 0
52+
j:= 0
53+
54+
for ;i<n;i++ {
55+
j = 1
56+
for ;j<n;j++ {
57+
sum+= i *j
58+
}
59+
}
60+
```
61+
可以看到 循环最多的代码就是在 `sum += i * j` 这里，不是 `i := 0` 因为它是常数级的代码， 也不是 `j = 1`, 因为它的复杂度是 n，我们观察 `sum += j *j` 就会发现，使用嵌套的代码复杂度等于里外复杂度之乘机可以得出，它执行了n * n = n^2 次，又根据，总复杂度等于量级最大的代码的复杂度，所以可以得出这段代码的时间复杂度是 `O(n^2) `
62+
63+
## 常见的时间复杂度
64+
- `O(1)` 常量级
65+
- `O(n)` 线性级
66+
- `O(log n)` 对数级
67+
- `O(n log n)` 线性对数级
68+
- `O(n^2)` 平方级
69+
- `O(n^3)` 立方级
70+
- `O(n^k)` k次放级
71+
- `O(2^n)` 指数级
72+
- `O(n!)` 阶乘级
73+
74+
其中后两个是非常低效的算法，谁这么写，就可以滚蛋了，所以不考虑这两种算法时间复杂度了。
75+
76+
常量级：
77+
78+
```go
79+
sum :=0
80+
i:= 0
81+
j:= 0
82+
```
83+
84+
线性级：
85+
86+
```go
87+
for i:= 0;i<n;i++ {
88+
sum+=i
89+
}
90+
```
91+
92+
线性级的特殊情况：
93+
94+
当算法里有m，n，并且它们俩无法获取规模时，必须使用 O(m+n) 的方式表示
95+
96+
```go
97+
for i:= 0;i<n;i++ {
98+
99+
}
100+
101+
for i:=0;i<m;i++ {
102+
}
103+
```
104+
105+
对数级和线性对数级：
106+
107+
```go
108+
i:= 1
109+
for i < n {
110+
i *= 2
111+
}
112+
```
113+
114+
最大值是n，从1开始每次都是乘以2，直到接近n结束，我们可以看每次的执行过程是 1 2 4 8 16 可以看出是以2为底数的次方增长的，那么它跟n的关系就是：2^i = n ,我们只需要知道i的次数增长趋势就获得了这次的复杂度，那么f(i) = log 2 n ，根据省略系数的原则，这次的时间复杂度就是 O(n) = logn
115+
116+
线性对数：
117+
118+
```go
119+
i:= 1
120+
for j:= 0;j < n ;j++ {
121+
for i < n {
122+
i *=2
123+
}
124+
}
125+
126+
```
127+
根据乘积原则，这段代码的时间复杂度是 nlogn
128+
129+
对数级的时间复杂度，是目前来说最佳的算法复杂度，因为常量级的复杂度本身几乎没什么意义，它没有变化的趋势，从趋势来说，一个无穷大的n，使用对数得到的值在众多算法中是最佳的。
130+
131+
![](./%E5%85%AC%E5%BC%8F.jpeg)
132+
133+
## 空间复杂度分析
134+
常见的空间复杂度有:
135+
- `O(1)`
136+
- `O(n)`
137+
- `O(n^2)`
138+
139+
`O(log n)` 和`O(nlog n)` 几乎不会用到，其它更多的也几乎遇不到。
140+
141+
142+
## 时间复杂度的几种概念
143+
- 最好时间复杂度
144+
- 最坏时间复杂度
145+
- 平均时间复杂度
146+
- 均摊时间复杂度
147+
148+
比如一个最基础的冒泡法排序算法
149+
150+
```go
151+
for i := 0; i < n;i++ {
152+
for j:=0;j<n-i-1;j++ {
153+
if arr[j] > arr[j+1] {
154+
swap(arr,j,j+1)
155+
}
156+
}
157+
}
158+
```
159+
160+
最好时间复杂度:
161+
162+
- 最理想的情况下，执行这段代码的时间复杂度，比如排序算法的时候，第一个就找到了，😂
163+
164+
最坏时间复杂度:
165+
166+
- 最糟糕的情况下的时间复杂度，比如排序算法的时候，找到最后一个才是要找的数据
167+
168+
平均时间复杂度:
169+
170+
- **平常用的那个就是平均时间复杂度**，因为大o法是要省略常数，系数，低阶的，所以使用概率去算出来的平均时间复杂度省略完成以后还是那个
171+
172+
使用冒泡法举一个例子：
173+
174+
((1 + 2 + ..+n)/n)*n ,结果算出来的去掉各种系数还是O(n^2)
175+
176+
177+
均摊时间复杂度:
178+
179+
- 举个例子，一个算法有插入操作，每次的`O(n)`操作，就跟着 n-1 次的O(1) 的插入操作， 将n平均分摊到n-1 的上面，那么得到的均摊时间复杂度就还是o(1) 这就是均摊时间复杂度。
180+
181+
这里给出排序算法的 平均时间复杂度,最好时间复杂度，最坏时间复杂度。
182+
183+
1. [冒泡排序](../排序算法/冒泡排序.md) `O(n^2)` `O(n)` `O(n^2)`
184+
2. 选择排序 `O(n^2)` `O(n^2)` `O(n^2)`
185+
3. 插入排序 `O(n^2)` `O(n)` `O(n^2)`
186+
4. 希尔排序 `O(nlogn)` `O(n(logn)^2)` `O(n(logn)^2)`
187+
5. 归并排序 `O(nlogn)` `O(nlogn)` `O(nlogn)`
188+
6. 快速排序 `O(nlogn)` `O(nlogn)` `O(n^2)`
189+
7. 堆排序 `O(nlogn)` `O(nlogn)` `O(nlogn)`
190+
8. 计数排序 `O(n+k)` `O(n+k)` `O(n+k)`
191+
9. 桶排序 `O(n+k)` `O(n+k)` `O(n^2)`
192+
10. 基数排序 `O(n*k)` `O(n*k)` `O(n*k)`
193+
194+
## 如何寻找最好的算法
195+
196+
## 通过排序算法的案例去讨论复杂度
197+
198+
199+
## 参考资料
200+
- [《计算之魂》](https://book.douban.com/subject/35641088/) 24 - 58
201+
- [《数据结构与算法之美》](https://time.geekbang.org/column/intro/100017301)03，04
202+
203+
204+

‎算法/算法/o/公式.jpeg

58.6 KB
Loading

‎算法/算法/排序算法/README.md

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,12 @@
11
# 排序算法
2+
- [冒泡排序](./冒泡排序.md)
3+
- [插入排序](./插入排序.md)
4+
- [希尔排序](./希尔排序.md)
5+
- [归并排序](./归并排序.md)
26
- [快排](./快排.md)
7+
- [堆排序](./堆排序.md)
8+
- [计数排序](./计数排序.md)
9+
- [桶排序](./桶排序.md)
10+
- [基数排序](./基数排序.md)
11+
312

‎算法/算法/排序算法/冒泡排序.md

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
# 冒泡排序
2+
## 基本原理
3+
按照最原始的方式，前者比后者大，那么就把前后调换一下顺序，然后第二个继续往后比较，直到把最大的换到最后面，这个时候最后那一位已经是确认要输出的值了，不能动了，所以再次从头开始继续这个过程，然后倒数第二个也是要输出的值了，往复循环，直到所有的数据都排好即可。
4+
![](https://raw.githubusercontent.com/imgoogege/Sorting-Algorithm/master/res/bubbleSort.gif)
5+
## 实现代码
6+
```go
7+
package main
8+
9+
import "fmt"
10+
11+
12+
func BubbleSort[T numbers](arr []T) []T {
13+
for i := 0; i < len(arr); i++ {
14+
for j := 0; j < len(arr)-1-i; j++ {
15+
if arr[j] > arr[j+1] {
16+
arr[j], arr[j+1] = arr[j+1], arr[j]
17+
}
18+
19+
}
20+
21+
}
22+
return arr
23+
}
24+
25+
26+
func main() {
27+
28+
fmt.Println(BubbleSort[int]([]int{4, 5, 3, 2}))
29+
fmt.Println(BubbleSort[float32]([]float32{4.0, 5.0, 3.1, 2.1}))
30+
}
31+
32+
type numbers interface {
33+
~int8 | ~uint8 | ~uint16 | ~int16 | ~uint32 | ~int32 | ~uint64 | ~int64 | ~int | ~uint |
34+
35+
~float64 | ~float32
36+
}
37+
38+
```
39+
```bash
40+
[2 3 4 5]
41+
[2.1 3.1 4 5]
42+
```
43+
## 时间复杂度分析
44+
### 平均时间复杂度
45+
最外层肯定是要循环n次的，那么里面要循环几次呢，第一次是1次，第二次是2次，第三次是3次...n次，那么可以得出来，内部循环的平均次数是
46+
(1+2...n)/n ,然后最终的次数是 1+2...n / n *n ,最终计算出来的平均时间复杂度就是 `o(n^2)`
47+
### 最好时间复杂度
48+
假设内部循环每次都是常数量级的交换，那么内部的时间复杂度就是o(1),根据内外相乘的原理，最好的时间复杂度就是 o(n)
49+
### 最坏时间复杂度
50+
假设内部的时间复杂度每次都是n次，那么最终算出来的结果就是 o(n^2)
51+
## 空间复杂度
52+
不需要申请其余的内存空间，所以是o(1)
53+
## 参考资料
54+
- https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/1.bubbleSort.md

‎算法/算法/排序算法/基数排序.md

Whitespace-only changes.

‎算法/算法/排序算法/堆排序.md

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
<!--
2+
* @Author: shgopher shgopher@gmail.com
3+
* @Date: 2023-01-12 19:07:02
4+
* @LastEditors: shgopher shgopher@gmail.com
5+
* @LastEditTime: 2023-01-12 19:09:29
6+
* @FilePath: /408/算法/算法/排序算法/堆排序.md
7+
* @Description:
8+
*
9+
* Copyright (c) 2023 by shgopher shgopher@gmail.com, All Rights Reserved.
10+
-->
11+
# 堆排序
12+
## 基本原理
13+
## 实现代码
14+
## 时间复杂度分析
15+
### 平均时间复杂度
16+
### 最好时间复杂度
17+
### 最坏时间复杂度

‎算法/算法/排序算法/希尔排序.md

Whitespace-only changes.

‎算法/算法/排序算法/归并排序.md

Whitespace-only changes.

0 commit comments

Comments
 (0)
0