package main
import "fmt"
func main() {
//有序度是数组中具有有序关系的元素对的个数。有序元素对用数学表达式就是这样
//有序元素对：a[i]<=a[j],如果i<j
//例如2,4,5,3,6,1,9的有序元素对就是2,4 2,5 2,3 2,6 2,9 4,5 4,6 4,9 5,6 5,9 3,6 3,9 6,9 1,9有序度就是14
//满有序度是n*(n-1)/2 = 21 逆序度=满有序度-有序度 = 7 也就是要交换7次 exchange=7
//对于冒泡排序的交换次数最好情况下是0，也就是说这个需要排序的数组初始状态下的有序度是n*(n-1)/2
//最坏情况下是n*(n-1)/2,也就是说初始有序度是0
//可以取个中间值n*(n-1)/4来表示初始有序度既不是很高也不是很低的平均情况
maopao()
charu()
}
/**
冒泡排序
*/
func maopao() {
var a = []int{2, 4, 5, 3, 6, 1, 9}
len_a := len(a)
var i, j, exchange int
var flag bool = false
for i = 0; i < len_a; i++ {
for j = 0; j < len_a-i-1; j++ {
if (a[j] > a[j+1]) {
a[j+1], a[j] = a[j], a[j+1]
exchange++
}
flag = true
}
if (!flag) {
break
}
}
fmt.Println("冒泡排序:", a, exchange)
}
/**
插入排序
*/
func charu() {
//插入排序的核心思想是把数据分成两部分，已排序区间和未排序区间，初始已排序区间只有一个数据，就是数组的第一个元素
//然后去未排序区间找一个数据，把它放在已排序区间合适的位置以后，然后在移动已排序区间的元素，重复这个过程直到有序
var a = []int{2, 4, 5, 3, 6, 1, 9}
len_a := len(a)
var i, j, tmp int
for i = 1; i < len_a; i++{
tmp = a[i]
j = i - 1
for ; j >= 0; j-- {
if (a[j] > tmp) {
a[j+1] = a[j]
} else {
break
}
}
a[j+1] = tmp
}
fmt.Println("选择排序:", a)
}