冒泡排序
冒泡排序是一种最简单的交换排序算法。
什么是交换？交换就是两两进行比较，如果不满足次序就可以交换位置。比如，我们想要从小到大排序，通过两个位置上的值两两比较，如果逆序就交换，使关键字大的记录像泡泡一样冒出来放在末尾。
重复执行若干次冒泡排序，最终得到有序序列。
冒泡排序的名字来源于：值较小的元素如同”气泡“一样逐渐漂浮到序列的顶端。
思想
- 给定一个N个元素的数组，冒泡法排序将：
如果元素大小关系不正确，交换这两个数（在本例中为a> b），
- 比较一对相邻元素（a，b），
- 重复步骤1和2，直到我们到达数组的末尾（最后一对是第（N-2）和（N-1）项，因为我们的数组从零开始）
- 到目前为止，最大的元素将在最后的位置。 然后我们将N减少1，并重复步骤1，直到N = 1。
动画演示
给定一个数组 29, 10, 14, 37, 14, 48, 17 ，经过冒泡排序的动画如下所示：
代码实现
package main import "fmt" func main() { // index starts from 0 var nums = []int{29, 10, 14, 37, 14, 48, 17} var length = len(nums) fmt.Println("原数组：", nums) bubbleSort(nums, length) fmt.Print("数组排序后:") for i := 0; i < length; i++ { fmt.Printf("%d\t", nums[i]) } } func bubbleSort(nums []int, length int) { for i := 0; i < length-1; i++ { for j := 0; j < length-i-1; j++ { if nums[j] > nums[j+1] { // 如果大，交换 var temp = nums[j] // 临时变量保存前一个值 nums[j] = nums[j+1] nums[j+1] = temp } } } }
运行上述代码，可以看到排序的结果：
[Running] go run "e:\Coding Workspaces\LearningGoTheEasiestWay\Go 数据结构\冒泡排序\main.go" 原数组： [29 10 14 37 14 48 17] 数组排序后:10 14 14 17 29 37 48
冒泡排序的优化
可以附加一个标志来改进该算法，在排序过程中，如果没有交换操作意味着排序完成。如果序列已经是有序的，则可以通过判断该标记来结束算法。
func bubbleSortImproved(nums []int, length int) { swapped := true for i := 0; i < length-1; i++ { for j := 0; j < length-i-1; j++ { if nums[j] > nums[j+1] { // 如果大，交换 var temp = nums[j] // 临时变量保存前一个值 nums[j] = nums[j+1] nums[j+1] = temp swapped = false //如果没有出现这步骤,说明没有需要交换的了 } } if swapped { // 从头到尾都没有进行交换，说明已经排序完成 break } } }
在最好情况下，改进的冒泡算法的时间复杂度为
网络异常，图片无法展示
|
优化二，记录发生交换的位置
func BubbleBestSort(a []int) { lastSwap := len(a) - 1 lastSwapTemp := len(a) - 1 for j := 0; j < len(a)-1; j++ { lastSwap = lastSwapTemp for i := 0; i < lastSwap; i++ { if a[i] > a[i+1] { a[i], a[i+1] = a[i+1], a[i] lastSwapTemp = i } } if lastSwap == lastSwapTemp { break } }
总结
想对比其他排序算法的优点是，它能够检测输入序列是否已经是排序的。
