算法 - 冒泡排序

• 源码

• 代码

// 对data进行正向排序
// 每一趟都把最大的元素移到最后。
// 1、比较相邻的2个元素，如果前一个比后一个大，就交换2个元素；
// 2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对；
// 3、针对所有的元素重复以上的步骤，除了最后一个；
// 4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
// 设置swap交换标志位可提供效率。
// 难度系数 O(n^2)
//
func BubbleSort(data []int) {
    // 交换标志
    swap := false
    for i := 0; i < len(data)-1; i++ {
        swap = false
        for j := 0; j < len(data)-i-1; j++ {
            if data[j] > data[j+1] {
                data[j], data[j+1] = data[j+1], data[j]
                swap = true
            }
        }
        if !swap {
            break
        }
    }
}

• 测试

func TestBubbleSort(t *testing.T) {
    data := []int{1, 0, 35, 9, 7, 8, 5, 4, 3, 33}
    fmt.Println("sort before", data)
    sort2.BubbleSort(data)
    fmt.Println("sort after", data)
}

• 分析

sort before [1 0 35 9 7 8 5 4 3 33]
i j data swap
0 0 [1 0 35 9 7 8 5 4 3 33] false
0 1 [0 1 35 9 7 8 5 4 3 33] true
0 2 [0 1 35 9 7 8 5 4 3 33] true
0 3 [0 1 9 35 7 8 5 4 3 33] true
0 4 [0 1 9 7 35 8 5 4 3 33] true
0 5 [0 1 9 7 8 35 5 4 3 33] true
0 6 [0 1 9 7 8 5 35 4 3 33] true
0 7 [0 1 9 7 8 5 4 35 3 33] true
0 8 [0 1 9 7 8 5 4 3 35 33] true
1 0 [0 1 9 7 8 5 4 3 33 35] false
1 1 [0 1 9 7 8 5 4 3 33 35] false
1 2 [0 1 9 7 8 5 4 3 33 35] false
1 3 [0 1 7 9 8 5 4 3 33 35] true
1 4 [0 1 7 8 9 5 4 3 33 35] true
1 5 [0 1 7 8 5 9 4 3 33 35] true
1 6 [0 1 7 8 5 4 9 3 33 35] true
1 7 [0 1 7 8 5 4 3 9 33 35] true
2 0 [0 1 7 8 5 4 3 9 33 35] false
2 1 [0 1 7 8 5 4 3 9 33 35] false
2 2 [0 1 7 8 5 4 3 9 33 35] false
2 3 [0 1 7 8 5 4 3 9 33 35] false
2 4 [0 1 7 5 8 4 3 9 33 35] true
2 5 [0 1 7 5 4 8 3 9 33 35] true
2 6 [0 1 7 5 4 3 8 9 33 35] true
3 0 [0 1 7 5 4 3 8 9 33 35] false
3 1 [0 1 7 5 4 3 8 9 33 35] false
3 2 [0 1 7 5 4 3 8 9 33 35] false
3 3 [0 1 5 7 4 3 8 9 33 35] true
3 4 [0 1 5 4 7 3 8 9 33 35] true
3 5 [0 1 5 4 3 7 8 9 33 35] true
4 0 [0 1 5 4 3 7 8 9 33 35] false
4 1 [0 1 5 4 3 7 8 9 33 35] false
4 2 [0 1 5 4 3 7 8 9 33 35] false
4 3 [0 1 4 5 3 7 8 9 33 35] true
4 4 [0 1 4 3 5 7 8 9 33 35] true
5 0 [0 1 4 3 5 7 8 9 33 35] false
5 1 [0 1 4 3 5 7 8 9 33 35] false
5 2 [0 1 4 3 5 7 8 9 33 35] false
5 3 [0 1 3 4 5 7 8 9 33 35] true
6 0 [0 1 3 4 5 7 8 9 33 35] false
6 1 [0 1 3 4 5 7 8 9 33 35] false
6 2 [0 1 3 4 5 7 8 9 33 35] false
sort after [0 1 3 4 5 7 8 9 33 35]