冒泡排序

[hunterhug]

https://hunterhug.github.io/goa.c/#/algorithm/sort/bubble_sort

Description

[baici1]

我觉得通过文字去描述这个排序的流程有点繁琐，不直观，可以采用动画的方式。
推荐一波：https://visualgo.net/zh/sorting
你可以将上诉的过程描述换成下图。

[hunterhug]

@baici1
我觉得通过文字去描述这个排序的流程有点繁琐，不直观，可以采用动画的方式。
推荐一波：https://visualgo.net/zh/sorting
你可以将上诉的过程描述换成下图。

这个网站也可以：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

画图能力抓急，所以大部分都是文字描述。

[baici1]

这个网站也可以：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

画图能力抓急，所以大部分都是文字描述。

你不用画图，用录屏的方式生成gif，文字描述之后贴一个动画会能更好的解释。

[hunterhug]

@baici1

这个网站也可以：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

画图能力抓急，所以大部分都是文字描述。

你不用画图，用录屏的方式生成gif，文字描述之后贴一个动画会能更好的解释。

我等补充一下。

[baici1]

放开她，让我来！！哈哈哈让这个项目旁边有我的人头！

[hunterhug]

放开她，让我来！！哈哈哈让这个项目旁边有我的人头！

给你机会，你可以的

[Carlos9986]

菜鸡提问：关于提前结束循环的控制变量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)
}

[hunterhug]

菜鸡提问：关于提前结束循环的控制变量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放在外层和内层是没区别，放在外层不需要频繁创建临时变量。你仔细想一想。