goa.c
goa.c copied to clipboard
hunterhug
冒泡排序
https://hunterhug.github.io/goa.c/#/algorithm/sort/bubble_sort
Description
我觉得通过文字去描述这个排序的流程有点繁琐，不直观，可以采用动画的方式。
推荐一波：https://visualgo.net/zh/sorting
你可以将上诉的过程描述换成下图。
@baici1 我觉得通过文字去描述这个排序的流程有点繁琐，不直观，可以采用动画的方式。 推荐一波：https://visualgo.net/zh/sorting 你可以将上诉的过程描述换成下图。
这个网站也可以：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
画图能力抓急，所以大部分都是文字描述。
这个网站也可以：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
画图能力抓急，所以大部分都是文字描述。
你不用画图，用录屏的方式生成gif，文字描述之后贴一个动画会能更好的解释。
@baici1
这个网站也可以：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
画图能力抓急，所以大部分都是文字描述。
你不用画图，用录屏的方式生成gif，文字描述之后贴一个动画会能更好的解释。
我等补充一下。
菜鸡提问：关于提前结束循环的控制变量didSwap的位置及功能的问题： 1.原代码中didSwap的位置代表的功能：查看第一轮交换是否发生交换行为，如果发生就继续进行冒泡排序，如果没有发生，说明原序列是排序好的，就结束循环。 2.改变didSwap的位置，可以检查每一轮交换中是否发生交换行为，一旦没有，则说明已经排序好了，就立即结束循环。
代码如下：
package main
import "fmt"
func BubbleSort(list []int) {
n := len(list)
// 在一轮中有没有交换过
didSwap := false
// 进行 N-1 轮迭代
for i := n - 1; i > 0; i-- {
// 每次从第一位开始比较，比较到第 i 位就不比较了，因为前一轮该位已经有序了
for j := 0; j < i; j++ {
// 如果前面的数比后面的大，那么交换
if list[j] > list[j+1] {
list[j], list[j+1] = list[j+1], list[j]
didSwap = true
}
}
// 如果在一轮中没有交换过，那么已经排好序了，直接返回
if !didSwap {//note：感觉这个didSwap只能验证第一轮是否发生交换，发生就继续，没发生说明本来就是排好序的，就结束循环
return
}
}
}
func BubbleSort2(list []int) {
n := len(list)
// 进行 N-1 轮迭代
for i := n - 1; i > 0; i-- {
didSwap := false
// 每次从第一位开始比较，比较到第 i 位就不比较了，因为前一轮该位已经有序了
for j := 0; j < i; j++ {
// 如果前面的数比后面的大，那么交换
if list[j] > list[j+1] {
list[j], list[j+1] = list[j+1], list[j]
didSwap = true
}
// 每一轮都验证，若没有发生交换，说明已经排好序，立即结束
if !didSwap {
//break
return
}
}
}
}
func main() {
list := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
BubbleSort(list)
fmt.Println("BubbleSort(list):",list)
BubbleSort2(list)
fmt.Println("BubbleSort2(list):",list)
}
菜鸡提问：关于提前结束循环的控制变量didSwap的位置及功能的问题： 1.原代码中didSwap的位置代表的功能：查看第一轮交换是否发生交换行为，如果发生就继续进行冒泡排序，如果没有发生，说明原序列是排序好的，就结束循环。 2.改变didSwap的位置，可以检查每一轮交换中是否发生交换行为，一旦没有，则说明已经排序好了，就立即结束循环。
代码如下：
package main import "fmt" func BubbleSort(list []int) { n := len(list) // 在一轮中有没有交换过 didSwap := false // 进行 N-1 轮迭代 for i := n - 1; i > 0; i-- { // 每次从第一位开始比较，比较到第 i 位就不比较了，因为前一轮该位已经有序了 for j := 0; j < i; j++ { // 如果前面的数比后面的大，那么交换 if list[j] > list[j+1] { list[j], list[j+1] = list[j+1], list[j] didSwap = true } } // 如果在一轮中没有交换过，那么已经排好序了，直接返回 if !didSwap {//note：感觉这个didSwap只能验证第一轮是否发生交换，发生就继续，没发生说明本来就是排好序的，就结束循环 return } } } func BubbleSort2(list []int) { n := len(list) // 进行 N-1 轮迭代 for i := n - 1; i > 0; i-- { didSwap := false // 每次从第一位开始比较，比较到第 i 位就不比较了，因为前一轮该位已经有序了 for j := 0; j < i; j++ { // 如果前面的数比后面的大，那么交换 if list[j] > list[j+1] { list[j], list[j+1] = list[j+1], list[j] didSwap = true } // 每一轮都验证，若没有发生交换，说明已经排好序，立即结束 if !didSwap { //break return } } } } func main() { list := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3} BubbleSort(list) fmt.Println("BubbleSort(list):",list) BubbleSort2(list) fmt.Println("BubbleSort2(list):",list) }
其实把didSwap放在外层和内层是没区别，放在外层不需要频繁创建临时变量。你仔细想一想。