算法:冒泡排序法的原理

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

下面用流程来描述冒泡排序的运作过程:
假设有一个数组 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

  • 第一次大循环
大循环 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;

可以看出,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]

你可能感兴趣的