目录
前言
冒泡排序
代码示例
1. 算法包
2. 冒泡排序代码
3. 模拟排序
4. 运行程序
5. 从大到小排序
循环细节
外层循环
内层循环
总结
循环次数测试
假如 10 条数据进行排序
假如 20 条数据进行排序
假如 30 条数据进行排序
假设 5000 条数据,对比 选择、插入、快速、堆、归并
冒泡排序的适用场景
1. 数据量非常小
2. 数据几乎有序
3. 教学用途
4. 稳定性
前言
在实际场景中,选择合适的排序算法对于提高程序的效率和性能至关重要,本节课主要讲解"冒泡排序"的适用场景及代码实现。
冒泡排序
冒泡排序(Bubble Sort) 是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢"浮"到数列的顶端。
代码示例
下面我们使用Go语言实现一个冒泡排序:
1. 算法包
创建一个 pkg/algorithm.go
touch pkg/algorithm.go
2. 冒泡排序代码
打开 pkg/algorithm.go 文件,代码如下
从小到大 排序
package pkg// BubbleSort 冒泡排序
func BubbleSort(arr []int) {n := len(arr) // 获取切片长度for i := 0; i < n-1; i++ { // 外层循环控制遍历的次数for j := 0; j < n-i-1; j++ { // 内层循环控制每轮遍历的次数,每完成一轮,最大数就“冒泡”到最后if arr[j] > arr[j+1] { // 比较相邻元素,如果前一个比后一个大,则交换arr[j], arr[j+1] = arr[j+1], arr[j] // 两个元素换位置}}}
}
3. 模拟排序
打开 main.go 文件,代码如下:
package mainimport ("demo/pkg""fmt"
)func main() {// 定义一个切片,这里我们模拟 10 个元素arr := []int{999, 452, 37, 1573, 234, 5, 318, 76483, 115, 86}fmt.Println("Original data:", arr) // 先打印原始数据pkg.BubbleSort(arr) // 调用冒泡排序fmt.Println("New data: ", arr) // 后打印排序后的数据
}
4. 运行程序
打开终端,我们运行 go :
go run main.go
能发现, Original data 后打印的数据,正是我们代码中定义的切片数据,顺序也是一致的。
New Data 后打印的数据,则是经过冒泡排序后的数据,是从小到大的。
5. 从大到小排序
如果需要 从大到小 排序也是可以的,在代码里,将两个元素比较的 大于符号 改成 小于符号 即可。
修改 pkg/algorithm.go 文件:
package pkg// BubbleSort 冒泡排序
func BubbleSort(arr []int) {n := len(arr) // 获取切片长度for i := 0; i < n-1; i++ { // 外层循环控制遍历的次数for j := 0; j < n-i-1; j++ { // 内层循环控制每轮遍历的次数,每完成一轮,最大数就“冒泡”到最后if arr[j] < arr[j+1] { // 比较相邻元素,如果前一个比后一个大,则交换arr[j], arr[j+1] = arr[j+1], arr[j] // 两个元素换位置}}}
}
只需要一丁点的代码即可
在第八行代码中,我们将 ">" 改成了 "<" ,这样就变成了 从大到小排序了
循环细节
心细的同学已经发现,我们的外层循环中,有 "n - 1",而内层循环中,有 "n - i - 1"
外层循环
外层循环控制的是遍历数组的总轮数。在冒泡排序中,没完成一轮遍历,都会确保至少有一个元素被放置到它最终的位置上。因此,随着排序的进行,未排序的元素数量逐渐减少。
- 初始时,未排序的元素是整个数组,长度为 n
- 第一轮遍历后,最大的元素被放到了数组的最后一位,因此未排序的元素减少了一个,剩下 n - 1 个
- 第二轮遍历后,第二大的元素被放到了倒数第二个,未排序的元素再减少一个,剩下 n - 2 个
- 以此类推,直到所有的元素都排序完成
因此,外层循环的次数是 n - 1,即
for i := 0; i < n - 1; i ++ {}
内层循环
内层循环负责在每一轮遍历中,通过相邻元素的比较和交换,将未排序部分的最大元素"冒泡"到其正确位置。随着外层循环的进行,每一轮结束后,数组的末尾都会增加一个已排序的元素(即最大元素),因此内层循环的遍历范围需要相应减少。
- 初始时,内层循环需要遍历整个未排序的数组,即 j 从 0 到 n - 1。但由于每次遍历结束时,最后一个元素都会是未排序部分的最大值,所以实际上内层循环只需要遍历到 n - 2 (因为最后一个元素已经是最大的了,无需再比较)
- 随着外层循环的进行(即 i 的增加),每一轮结束时,数组的末尾都会增加一个已排序的元素,因此,每进入下一轮外层循环,内层循环的遍历范围就可以减少一个元素,即 n - i - 1
综上,内层循环的条件是
for j := 0; j < n - i - 1; j ++ {}
这里的 n - i - 1 确保了内层循环每次只遍历当前未排序的部分。
总结
外层循环的减 1 是因为每轮排序后,都有一个元素被确定位置,不需要再参与后续的排序;
内层循环的减 1 和减 i 是因为随着排序的进行,未排序的元素数量在逐渐减少,需要相应地调整遍历范围。
循环次数测试
按照上面示例进行测试:
假如 10 条数据进行排序
外层循环了 9 次
内层循环了 45 次
总计循环了 54 次
假如 20 条数据进行排序
外层循环了 19 次
内层循环了 190 次
总计循环了 209 次
假如 30 条数据进行排序
外层循环了 29 次
内层循环了 435 次
总计循环了 464 次
...
会发现,仅仅只是增加了 10 条数据,或者是 20 条数据,循环次数则是成几倍甚至十倍增长,所以数据量稍微多一点,是不建议使用 冒泡排序
假设 5000 条数据,对比 选择、插入、快速、堆、归并
- 冒泡排序:循环次数 12,502,499 次
- 选择排序:循环次数 12,502,499 次
- 插入排序:循环次数 6,323,958 次
- 快速排序:循环次数 74,236 次
- 堆排序:循环次数 59,589 次
- 归并排序:循环次数 60,288 次
冒泡排序的适用场景
尽管冒泡排序在大多数情况下并不是最高效的排序算法(其平均和最坏情况时间复杂度均为 O( n ^ 2),其中 n 是数组的长度),但在某些特定场景下,它仍然有其应用价值
1. 数据量非常小
当需要排序的数据量非常小时,冒泡排序的简单性可能会使其成为一种快速且易于实现的解决方案
2. 数据几乎有序
如果数据已经是接近排序的状态,那么冒泡排序的效率会相对较高,因为它在遍历过程中可以迅速地将大部分元素排序好,从而减少后续遍历的次数
3. 教学用途
由于其算法简单易懂,冒泡排序经常被用作教学算法,帮助学生理解排序算法的基本思想和过程
4. 稳定性
冒泡排序是一种稳定的排序算法,即如果两个相等的元素在排序前的相对顺序和在排序后的相对顺序相同。在某些需要保持元素原始的场合,冒泡排序可能是一个合适的选择
综上所述,虽然冒泡排序在大多数情况下不是最优选择,但在特定场景下,它仍然有其独特的优势和价值。