/ Go 语言实现冒泡排序完全指南 /
本文将手把手教你使用 Go 语言实现冒泡排序,并提供完整的示例代码。
1
1. 冒泡排序原理
冒泡排序的基本思想是:
- 从左到右不断交换相邻逆序的元素
- 一轮下来,最大元素会交换移到右端
- 对除最后元素外的子序列,重复步骤 1
- 若没有发生交换,说明序列已排序完成
以数组 [5, 1, 4, 2, 3] 为例:
[5, 1, 4, 2, 3] -> [1, 5, 4, 2, 3] [1, 5, 4, 2, 3] -> [1, 4, 5, 2, 3] [1, 4, 5, 2, 3] -> [1, 4, 2, 5, 3] [1, 4, 2, 5, 3] -> [1, 4, 2, 3, 5]
重复轮数直到完全有序。
2
2. 基本实现
冒泡排序标准实现:
func bubbleSort(nums []int) { for i := 0; i < len(nums); i++ { for j := 1; j < len(nums)-i; j++ { if nums[j] < nums[j-1] { nums[j], nums[j-1] = nums[j-1], nums[j] } } } }
内层循环处理交换,外层循环控制轮数。
3
3. 优化方法
设置标志提前退出
func bubbleSort(nums []int) { for i := 0; i < len(nums); i++ { swapped := false for j := 1; j < len(nums)-i; j++ { if nums[j] < nums[j-1] { nums[j], nums[j-1] = nums[j-1], nums[j] swapped = true } } if !swapped { break } } }
如果没有交换发生则提前退出。
记录最后交换位置
func bubbleSort(nums []int) { for i := 0; i < len(nums); i++ { lastSwapIndex := 0 for j := 1; j < len(nums)-i; j++ { if nums[j] < nums[j-1] { nums[j], nums[j-1] = nums[j-1], nums[j] lastSwapIndex = j } } if lastSwapIndex == 0 { break } } }
记录最后一次交换位置,次后仅需比较到这里。
4
4. 改进方法
鸡尾酒排序
func cocktailSort(nums []int) []int { for i := 0; i < len(nums)/2; i++ { nums = bubbleSortForward(nums) nums = bubbleSortBackward(nums) } return nums } // 正向冒泡 func bubbleSortForward(nums []int) []int { for i := 0; i < len(nums); i++ { for j := 1; j < len(nums)-i; j++ { if nums[j] < nums[j-1] { nums[j], nums[j-1] = nums[j-1], nums[j] } } } return nums } // 反向冒泡 func bubbleSortBackward(nums []int) []int { n := len(nums) for i := 0; i < n; i++ { for j := n - 1; j > i; j-- { if nums[j] < nums[j-1] { nums[j], nums[j-1] = nums[j-1], nums[j] } } } return nums }
正反向交替冒泡,效率提升。
插入排序改进
func insertionBubbleSort(nums []int) { for i := 1; i < len(nums); i++ { insertIntoOrdered(nums, i) } } // 将nums[i]插入有序区间[0...i-1] func insertIntoOrdered(nums []int, i int) { for j := i - 1; j >= 0 && nums[j] > nums[j+1]; j-- { nums[j], nums[j+1] = nums[j+1], nums[j] } }
5
5. 复杂度分析
- 最优时间复杂度 O(n)
- 最坏时间复杂度 O(n^2)
- 平均时间复杂度 O(n^2)
- 空间复杂度 O(1)
冒泡排序是一种稳定的排序算法。
6
6. 拓展与优化
并行冒泡
func parallelBubbleSort(nums []int) { var wg sync.WaitGroup for i := 0; i < len(nums); i++ { wg.Add(1) go bubblePass(&wg, nums, i) } wg.Wait() } func bubblePass(wg *sync.WaitGroup, nums []int, i int) { defer wg.Done() for j := 1; j < len(nums)-i; j++ { if nums[j] < nums[j-1] { nums[j], nums[j-1] = nums[j-1], nums[j] } } }
并发进行多轮冒泡,效率提升。
可视化
import "github.com/faiface/pixel" func visualizeBubbleSort(nums []int) { for i := 0; i < len(nums); i++ { for j := 0; j < len(nums)-i-1; j++ { if nums[j] > nums[j+1] { // 交换两个元素 temp := nums[j] nums[j] = nums[j+1] nums[j+1] = temp // 绘制当前排序状态 drawBars(nums) } } } } func drawBars(nums []int) { canvas := pixel.NewCanvas(500, 500) barWidth := canvas.Bounds().W / float64(len(nums)) for i, v := range nums { x := float64(i) * barWidth h := float64(v) * 4 canvas.Rectangle(x, 500-h, barWidth, h) } canvas.Draw() // 暂停一小段时间 time.Sleep(time.Millisecond * 500) }
通过动画等可视化冒泡排序过程。
7
总结
这篇文章详细介绍了冒泡排序的原理、实现、分析和优化方法,每部分都以通俗易懂的语言和充足的代码进行讲解,全面帮助读者理解冒泡排序算法的方方面面。冒泡排序虽简单但启发意义深远,希望本文可以增进读者对算法和编码的理解。
