算法:冒泡排序法的原理
文章目录
冒泡排序的基本思想就是:从无序序列头部开始,进行两两比较,根据大小交换位置,直到最后将最大(小)的数据元素交换到了无序队列的队尾,从而成为有序序列的一部分;下一次继续这个过程,直到所有数据元素都排好序。
算法的核心在于每次通过两两比较交换位置,选出剩余无序序列里最大(小)的数据元素放到队尾
下面用流程来描述冒泡排序的运作过程:
假设有一个数组 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 设为 D0 设为 E
第一次大循环
| 大循环 | A | B | C | D | E | 小循环两两比较 |
|---|---|---|---|---|---|---|
| -1 | 2 | 7 | 3 | 0 | ||
| 第1次循环 | -1 | 2 | A和B | |||
| ......... | 2 | 7 | B和C | |||
| ......... | 3 | 7 | C和D | |||
| ......... | 0 | 7 | D和E | |||
| 结果 | -1 | 2 | 3 | 0 | 7 | 小循环比较4次 |
当进行第 1 循环时,对数组共排了 4 次
此时结果为 [-1, 2, 3, 0, 7]
第二次大循环
| 大循环 | A | B | C | D | E | 小循环两两比较 |
|---|---|---|---|---|---|---|
| -1 | 2 | 3 | 0 | 7 | ||
| 第2次循环 | -1 | 2 | A和B | |||
| ......... | 2 | 7 | B和C | |||
| ......... | 0 | 3 | C和D | |||
| 结果 | -1 | 2 | 0 | 3 | 7 | 小循环比较3次 |
当进行第 2 循环时,对数组共排了 3 次
此时结果为 [-1, 2, 0, 3, 7]
第三次大循环
| 大循环 | A | B | C | D | E | 小循环两两比较 |
|---|---|---|---|---|---|---|
| -1 | 2 | 0 | 3 | 7 | ||
| 第3次循环 | -1 | 2 | A和B | |||
| ......... | 0 | 2 | B和C | |||
| 结果 | -1 | 0 | 2 | 3 | 7 | 小循环比较3次 |
当进行第 3 循环时,对数组共排了 2 次
此时结果为 [-1, 0, 2, 3, 7]
第四次大循环
| 大循环 | A | B | C | D | E | 小循环两两比较 |
|---|---|---|---|---|---|---|
| -1 | 2 | 0 | 3 | 7 | ||
| 第4次循环 | -1 | 2 | A和B | |||
| 结果 | -1 | 0 | 2 | 3 | 7 | 小循环比较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;
可以看出,i 和 j 的关系为 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]
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论