冒泡排序的终极改进优化
1、排序方法
将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
（1）初始
R[1..n]为无序区。
（2）第一趟扫描
从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。即依次比较(R[n]，R[n-1])，(R[n-1]，R[n-2])，…，(R[2]，R[1])；对于每对气泡(R[j+1]，R[j])，若R[j+1].key<R[j].key，则交换R[j+1]和R[j]的内容。
第一趟扫描完毕时，"最轻"的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R[1]上。
（3）第二趟扫描
扫描R[2..n]。扫描完毕时，"次轻"的气泡飘浮到R[2]的位置上……
最后，经过n-1 趟扫描可得到有序区R[1..n]
注意：
第i趟扫描时，R[1..i-1]和R[i..n]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时，该区中最轻气泡飘浮到顶部位置R[i]上，结果是R[1..i]变为新的有序区。
2、冒泡排序过程动画演示
https://www.erdangjiade.com/jquery/75/7559/demo/
3. 传统实现
package main
import "fmt"
func buble(a []int) []int {
l := len(a)
fmt.Println("inputed ", a, " len ", l)
last := l - 1
tmp := 0
for i := l; i >= 0; i-- {
for j := 0; j < last; j++ {
if a[j] > a[j+1] {
tmp = a[j]
a[j] = a[j+1]
a[j+1] = tmp
}
}
}
return a
}
func main() {
a := []int{3, 7, 8, 11, 99}
fmt.Println("len ", len(a), buble(a))
a = []int{3, 7, 1, 4, 8, 2, 5, 11, 99, 7}
fmt.Println("len ", len(a), buble(a))
}inputed [3 7 8 11 99] len 5
len 5 [3 7 8 11 99]
inputed [3 7 1 4 8 2 5 11 99 7] len 10
len 10 [1 2 3 4 5 7 7 8 11 99]改进后：
package main
import "fmt"
func buble(a []int) []int {
l := len(a)
fmt.Println("inputed ", a, " len ", l)
tmp := 0
pos := 0
last := l - 1
for i := l; i >= 0; i-- {
swap := 0 //如果一趟循环没有发生过交换， 说明啥？ 那就是数组已经有序了，啥也不用做
for j := 0; j < last; j++ {
if a[j] > a[j+1] {
swap = 1
pos = j //最后一次交换发生时，那么后面的数组肯定是有序了，前面的数据则可能是无序的，所以记录这个位置，下次直接对比pos前面的
数即可，这就大大减少对比次数了inputed [3 7 8 11 99] len 5
len 5 [3 7 8 11 99]
inputed [3 7 1 4 8 2 5 11 99 7] len 10
len 10 [1 2 3 4 5 7 7 8 11 99]import "fmt"
func buble(a []int) []int {
l := len(a)
fmt.Println("inputed ", a, " len ", l)
pos := 0
last := l - 1
for i := l; i >= 0; i-- {
swap := 0
for j := 0; j < last; j++ {
if a[j] > a[j+1] {
swap = 1
pos = j
a[j] ^= a[j+1] //如果数组元素是(u)int(16/32/64)，可以考虑使用这种方式：位的异或运算。好处是不用借助临时变量。
a[j+1] ^= a[j]
a[j] ^= a[j+1]
}
}
last = pos
if swap == 0 {
return a
}
}
return a
}
func main() {
a := []int{3, 7, 8, 11, 99}
fmt.Println("len ", len(a), buble(a))
a = []int{3, 7, 1, 4, 8, 2, 5, 11, 99, 7}
fmt.Println("len ", len(a), buble(a))
}inputed [3 7 8 11 99] len 5
len 5 [3 7 8 11 99]
inputed [3 7 1 4 8 2 5 11 99 7] len 10
len 10 [1 2 3 4 5 7 7 8 11 99]如果你有更好的算法，欢迎评补充！！
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-09-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读