冒泡排序(Bubble Sort)
冒泡排序也叫做起泡排序
执行流程
1 从头开始比较每一对相邻元素，如果第1个比第2个大，就交换它们的位置 ✓ 执行完一轮后，最末尾那个元素就是最大的元素
2 忽略 1 中曾经找到的最大元素，重复执行步骤 1，直到全部元素有序
//最坏、平均时间复杂度:O(n2) 最好时间复杂度:O(n)
//空间复杂度:O(1)
for end := len(this.Array) - 1; end > 0; end-- {
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
this.Swap(begin, begin-1)
}
}
}
冒泡排序 – 优化1
如果序列已经完全有序，可以提前终止冒泡排序,相当于提前进行终止
for end := len(this.Array) - 1; end > 0; end-- {
sorted := true
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
this.Swap(begin, begin-1)
sorted = false
}
}
if sorted{
break
}
}
冒泡排序 – 优化2
如果序列尾部已经局部有序，可以记录最后1次交换的位置，减少比较次数
for end := len(this.Array) - 1; end > 0; end-- {
sortedIndex := 1
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
this.Swap(begin, begin-1)
sortedIndex = begin
}
}
end = sortedIndex
}
golang 源码
package mysort
import "fmt"
type Sort struct {
Array []int
CmpCount int64
SwapCount int64
}
func (this *Sort) SortArray(array []int) {
this.Array = make([]int, len(array))
copy(this.Array, array)
}
func (this *Sort) SortFunc() {
if this.Array == nil || len(this.Array) < 2 {
return
}
}
func (this *Sort) ComWithIndex(i1, i2 int) int {
this.CmpCount++
return this.Array[i1] - this.Array[i2]
}
func (this *Sort) ComWithValue(v1, v2 int) int {
this.CmpCount++
return v1 - v2
}
func (this *Sort) Swap(i1, i2 int) {
this.SwapCount++
this.Array[i2], this.Array[i1] = this.Array[i1], this.Array[i2]
}
func (this *Sort)ToString() {
fmt.Println("排序比较次数",this.CmpCount,"排序交换次数",this.SwapCount)
}
package mysort
type BubbleSort struct {
Sort
}
func (this *BubbleSort) SortArray(array []int) {
this.Sort.SortArray(array)
}
func (this *BubbleSort) SortFunc() {
this.Sort.SortFunc()
for end := len(this.Array) - 1; end > 0; end-- {
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
this.Swap(begin, begin-1)
}
}
}
}
// 设置一个bool 的标志，判断是否进行过交换
func (this *BubbleSort) SortFunc1() {
this.Sort.SortFunc()
for end := len(this.Array) - 1; end > 0; end-- {
sorted := true
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
this.Swap(begin, begin-1)
sorted = false
}
}
if sorted{
break
}
}
}
func (this *BubbleSort) SortFunc2() {
this.Sort.SortFunc()
for end := len(this.Array) - 1; end > 0; end-- {
sortedIndex := 1
for begin := 1; begin <= end; begin++ {
if this.ComWithIndex(begin, begin-1) < 0 {
this.Swap(begin, begin-1)
sortedIndex = begin
}
}
end = sortedIndex
}
}
package main
import (
"fmt"
"iktolin.com/mysort"
"math/rand"
"time"
)
func main() {
var array []int
rand.Seed(time.Now().UnixNano())
for i := 0; i < 40; i++ {
x := rand.Intn(100)
array = append(array, x)
}
fmt.Println("排序前",array)
// 时间复杂度 O(n2)
bubbleSort := mysort.BubbleSort{}
bubbleSort.SortArray(array)
bubbleSort.SortFunc()
bubbleSort.ToString()
//fmt.Println(array)
// 使用bool 值判断是否进行过排序，适用于原来就是排好序的
bubbleSort1 := mysort.BubbleSort{}
bubbleSort1.SortArray(array)
bubbleSort1.SortFunc1()
bubbleSort1.ToString()
// 使用bool 值判断是否进行过排序，适用于其中有局部排好序的
bubbleSort2 := mysort.BubbleSort{}
bubbleSort2.SortArray(array)
bubbleSort2.SortFunc2()
bubbleSort2.ToString()
}
//排序前 [54 37 92 86 57 91 57 36 95 85 57 96 79 71 14 3 84 10 92 14 38 24 47 34 91 48 76 42 4 4 23 6 0 49 47 24 26 54 85 52]
//排序比较次数 780 排序交换次数 478
//排序比较次数 759 排序交换次数 478
//排序比较次数 689 排序交换次数 478
网友评论