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