Skip to main content
 首页 » 编程设计

Golang 实现冒泡排序

2022年07月19日137dyllove98

Golang 实现冒泡排序

本文实现冒泡排序,充分利用Go语言特性。

1. 冒泡排序

冒泡排序循环集合n次的排序算法,每次遍历一次集合。其检查第一个元素和第二个元素,如果第一个大于第二个则交换它们,整个过程重复执行该动作。

该算法时间复杂度为O(n*n),n为待排序元素个数,最坏情况是下面示例:

[9,8,7,6,5,4,3,2,1,0] 

对于完全是逆序数组,冒泡排序需要迭代10次。最好场景是O(n), 在这之间可考虑优化,第一次迭代之后,最大的已经排好序,下次就可以不比较它;这样每次遍历之后总长度就少一个。再者,如果一次遍历并没有任何交换则说明已经排好序了,可提前结束。

2. 实现

Go 提供了非常酷的交换机制————多变量同时赋值。同时增加交换标识,标识是否已经排好序。每次迭代检查第n个和第n+1个,如果前者大于后者则交换。

package sort 
 
import "fmt" 
 
func BubbleSort(data []int)  { 
	var swapped = true 
	j := 0 
	for swapped { 
		swapped = false 
		for i := 1; i < len(data)-j; i++ { 
			if data[i-1] > data[i] { 
				fmt.Printf("Swapping %d, %d\n",data[i-1] , data[i]) 
				data[i], data[i-1] = data[i-1], data[i] 
				swapped = true 
			} 
		} 
		j++ 
	} 
} 

测试代码:

package sort 
 
import ( 
	"fmt" 
	"testing" 
) 
 
func TestBubbleSort(t *testing.T) { 
	data := [] int {3,7,4,5,2,1,9} 
	fmt.Println(data) 
	BubbleSort(data) 
	fmt.Println(data) 
} 

运行程序会看到它交换了数组中值,直到最后最大值冒泡到顶部,最终得到排序过的数组。
运行结果:

=== RUN   TestBubbleSort 
[3 9 7 4 5 2 1] 
Swapping 9, 7 
Swapping 9, 4 
Swapping 9, 5 
Swapping 9, 2 
Swapping 9, 1 
Swapping 7, 4 
Swapping 7, 5 
Swapping 7, 2 
Swapping 7, 1 
Swapping 5, 2 
Swapping 5, 1 
Swapping 4, 2 
Swapping 4, 1 
Swapping 3, 2 
Swapping 3, 1 
Swapping 2, 1 
[1 2 3 4 5 7 9] 
--- PASS: TestBubbleSort (0.00s) 
PASS 

3. 总结

本文我们使用Go实现冒泡排序,使用多变量同时赋值特性,学习了冒泡排序算法。


本文参考链接:https://blog.csdn.net/neweastsun/article/details/107301026
阅读延展