冒泡排序是交换排序中最简单的一种算法。 算法思路:
第一轮遍历 [4, 2, 1, 3]
第二轮遍历 [2, 1, 3, 4]
第三轮遍历 [1, 2, 3, 4]
import "fmt" func main() { nums := [4]int{4, 2, 1, 3} fmt.Println("原数组:", nums) fmt.Println("--------------------------------") NormalBubbleSort(nums) } func NormalBubbleSort(nums [4]int) { for i := 0; i < len(nums)-1; i++ { for j := 0; j < len(nums)-i-1; j++ { if nums[j] > nums[j+1] { nums[j], nums[j+1] = nums[j+1], nums[j] } } fmt.Printf("第 %d 轮遍历后的数组:%v\n", i+1, nums) } fmt.Println("--------------------------------") fmt.Println("排序后的数组:", nums) }
执行结果:
原数组: [4 2 1 3]
--------------------------------
第 1 轮遍历后的数组:[2 1 3 4]
第 2 轮遍历后的数组:[1 2 3 4]
第 3 轮遍历后的数组:[1 2 3 4]
--------------------------------
排序后的数组: [1 2 3 4]
值得注意的一个地方是第二层循环的条件 j < len(nums)-i-1
,为什么会减去 i
,因为每轮遍历结束之后,都会有一个元素被固定到后面,因此再进行下一轮的时候,那个元素无须再进行比较。
算法遍历次数为 n -1,每次遍历时元素比较的次数依次为 n - 1、n - 2、n - 3、···、3、2、1,将所有次数求和 = 1 + 2 + 3 + ··· + n - 2 + n - 1= n - 1 * (n - 1 + 1) / 2 = (n² - 1) / 2,因此时间复杂度为 O(n²)。
上述例子中,对数组 [4,2,1,3] 进行排序,我们来看看对数组 [4,2,1,3,5] 进行排序,打印数组排序的变化过程中:
原数组: [4 2 1 3 5]
--------------------------------
第 1 轮遍历后的数组:[2 1 3 4 5]
第 2 轮遍历后的数组:[1 2 3 4 5]
第 3 轮遍历后的数组:[1 2 3 4 5]
第 4 轮遍历后的数组:[1 2 3 4 5]
--------------------------------
排序后的数组: [1 2 3 4 5]
不难看出,第三轮与第四轮遍历过程中,都没有进行元素交换位置的操作,对此我们可以推出一个结论,如果在一轮遍历中,没有进行元素交换位置的操作,那么此时数组的里所有元素都处于正确位置。 根据这个结论,我们可以对算法进行优化:
import "fmt" func main() { nums := [5]int{4, 2, 1, 3, 5} fmt.Println("原数组:", nums) fmt.Println("--------------------------------") BestBubbleSort(nums) } func BestBubbleSort(nums [5]int) { isSwapped := true for isSwapped { isSwapped = false for i := 0; i < len(nums)-1; i++ { if nums[i] > nums[i+1] { nums[i], nums[i+1] = nums[i+1], nums[i] isSwapped = true } } fmt.Println("遍历后的数组:", nums) } fmt.Println("--------------------------------") fmt.Println("排序后的数组:", nums) }
执行结果:
原数组:
--------------------------------
遍历后的数组: [2 1 3 4 5]
遍历后的数组: [1 2 3 4 5]
遍历后的数组: [1 2 3 4 5]
--------------------------------
排序后的数组: [1 2 3 4 5]
isSwapper
,作为第一层循环的条件,每轮遍历开始之后,将标记变量 isSwapper
赋值为 false
,如果在比较的过程中发生元素交换,则将标记变量 isSwapper
赋值为 true
。直到 isSwapper
为 false
时,数组的里所有元素都处于正确的位置,此时可以结束遍历了。本文首先对冒泡排序进行简单的介绍,然后通过图片演示冒泡排序的思路。普通冒泡排序算法一共要遍历 n - 1 轮,由测试用例 [4 2 1 3 5] 的结果可以推断出 如果在一轮遍历中,没有进行元素交换位置的操作,那么此时数组的里所有元素都处于正确位置。 根据这个结论,对算法进行优化,优化后的算法,最好的情况下时间复杂度为 O(N)。