3.9 冒泡排序

1. 冒泡排序

有序的数组是不存在逆序对的，非有序的则存在逆序对，只需要把逆序对交换一下即可

• 多趟扫描
• 每趟相邻项比较，如果是逆序对那么交换位置

2. 特点

• 稳定性：稳定
• 时间复杂度：O（n²）
• 空间复杂度：O（1）

3. 实现

//O(N²)
func BubbleSort(data []model.Comparable) {
	for i := 0; i < len(data); i++ {
		for j := 0; j < len(data)-i-1; j++ {
			if data[j].CompareTo(data[j+1])>0 {
				util.Swap(data, j, j+1)
			}
		}
	}
}

3.1. 测试

func TestBubbleSort(t *testing.T) {
	e0 := model.NewElement(0)
	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	e4 := model.NewElement(4)

	data := []model.Comparable{e2, e1, e3, e0, e4}
	fmt.Println(data)

	BubbleSort(data)
	fmt.Println(data)
}

4. 优化

• 如果某一趟中没有一次交换，那么说明已经有序了，直接退出

func BubbleSort2(data []model.Comparable) {
	for i := 0; i < len(data); i++ {
		ordered := true
		for j := 0; j < len(data)-i-1; j++ {
			if data[j].CompareTo(data[j+1]) > 0 {
				ordered = false
				util.Swap(data, j, j+1)
			}
		}
		if ordered {
			break
		}
	}
}

5. 参考

• 排序算法稳定性_百度百科