算法:冒泡排序法的原理

大步点点 · · 63 次点击 · · 开始浏览    
冒泡排序的基本思想就是:从无序序列头部开始,进行两两比较,根据大小交换位置,直到最后将最大(小)的数据元素交换到了无序队列的队尾,从而成为有序序列的一部分;下一次继续这个过程,直到所有数据元素都排好序。
算法的核心在于每次通过两两比较交换位置,选出剩余无序序列里最大(小)的数据元素放到队尾

下面用流程来描述冒泡排序的运作过程:
假设有一个数组 arr

package main
import "fmt"
func main() {
   var arr [5]int = [5]int{-1, 2, 7, 3, 0}
}

为了方便表示数据,我们将
-1设为 A
2 设为 B
7 设为 C
3 设为 D
0 设为 E

  • 第一次大循环
大循环ABCDE小循环两两比较
-12730
第1次循环-12 A和B
......... 27 B和C
......... 37 C和D
......... 07D和E
结果-12307小循环比较4次

当进行第 1 循环时,对数组共排了 4
此时结果为 [-1, 2, 3, 0, 7]

  • 第二次大循环
大循环ABCDE小循环两两比较
-12307
第2次循环-12 A和B
......... 27 B和C
......... 03 C和D
结果-12037小循环比较3次

当进行第 2 循环时,对数组共排了 3
此时结果为 [-1, 2, 0, 3, 7]

  • 第三次大循环
大循环ABCDE小循环两两比较
-12037
第3次循环-12 A和B
......... 02 B和C
结果-10237小循环比较3次

当进行第 3 循环时,对数组共排了 2
此时结果为 [-1, 0, 2, 3, 7]

  • 第四次大循环
大循环ABCDE小循环两两比较
-12037
第4次循环-12 A和B
结果-10237小循环比较1次

当进行第 4 循环时,对数组共排了 1
此时结果为 [-1, 0, 2, 3, 7]

总结
设数组长度为 len ,大循环次数为 i, 小循环次数为 j
i = 1 时,j = len - 1 = 4;
i = 2 时,j = len - 2 = 3;
i = 3 时,j = len - 3 = 2;
i = 4 时,j = len - 4 = 1;

可以看出,ij 的关系为 j = len - i
那么用代码表示就是

package main

import "fmt"

func main() {
   var arr [5]int = [5]int{-1, 2, 7, 3, 0}
   
   for i := 1; i < len(arr); i++ {  // 大循环
      for j := 0; j < len(arr) - i; j++ {  // 小循环,j = len - i
         if arr[j] > arr[j+1] {
            arr[j], arr[j+1] = arr[j+1], arr[j]
         }
      }
   }
   fmt.Println("新的arr = ", arr)
}

输出结果就是:

新的a =  [-1 0 2 3 7]

有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:大步点点

查看原文:算法:冒泡排序法的原理

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:1006366459

63 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传