package main
import (
"fmt"
"math/rand"
"time"
// "os"
// "os/signal"
)
const (
num = 100000
rangeNum = 100000
)
func main() {
randSeed := rand.New(rand.NewSource(time.Now().Unix() + time.Now().UnixNano()))
var buf []int
for i := 0; i < num; i++ {
buf = append(buf, randSeed.Intn(rangeNum))
}
t := time.Now()
//冒泡排序
// maopao(buf)
// 选择排序
// xuanze(buf)
// 插入排序
// charu(buf)
//希尔排序
// xier(buf)
//快速排序
// kuaisu(buf)
// 归并排序
// guibing(buf)
// 堆排序
duipai(buf)
// fmt.Println(buf)
fmt.Println(time.Since(t))
//等待退出
// c := make(chan os.Signal, 1)
// signal.Notify(c, os.Interrupt, os.Kill)
// <-c
// fmt.Println("Receive ctrl-c")
}
// 冒泡排序
func maopao(buf []int) {
times := 0
for i := 0; i < len(buf)-1; i++ {
flag := false
for j := 1; j < len(buf)-i; j++ {
if buf[j-1] > buf[j] {
times++
tmp := buf[j-1]
buf[j-1] = buf[j]
buf[j] = tmp
flag = true
}
}
if !flag {
break
}
}
fmt.Println("maopao times: ", times)
}
// 选择排序
func xuanze(buf []int) {
times := 0
for i := 0; i < len(buf)-1; i++ {
min := i
for j := i; j < len(buf); j++ {
times++
if buf[min] > buf[j] {
min = j
}
}
if min != i {
tmp := buf[i]
buf[i] = buf[min]
buf[min] = tmp
}
}
fmt.Println("xuanze times: ", times)
}
// 插入排序
func charu(buf []int) {
times := 0
for i := 1; i < len(buf); i++ {
for j := i; j > 0; j-- {
if buf[j] < buf[j-1] {
times++
tmp := buf[j-1]
buf[j-1] = buf[j]
buf[j] = tmp
} else {
break
}
}
}
fmt.Println("charu times: ", times)
}
// 希尔排序
func xier(buf []int) {
times := 0
tmp := 0
length := len(buf)
incre := length
// fmt.Println("buf: ", buf)
for {
incre /= 2
for k := 0; k < incre; k++ { //根据增量分为若干子序列
for i := k + incre; i < length; i += incre {
for j := i; j > k; j -= incre {
// fmt.Println("j: ", j, " data: ", buf[j], " j-incre: ", j-incre, " data: ", buf[j-incre])
times++
if buf[j] < buf[j-incre] {
tmp = buf[j-incre]
buf[j-incre] = buf[j]
buf[j] = tmp
} else {
break
}
}
// fmt.Println("middle: ", buf)
}
// fmt.Println("outer: ", buf)
}
// fmt.Println("outer outer: ", buf, " incre: ", incre)
if incre == 1 {
break
}
}
// fmt.Println("after: ", buf)
fmt.Println("xier times: ", times)
}
// 快速排序
func kuaisu(buf []int) {
kuai(buf, 0, len(buf)-1)
}
func kuai(a []int, l, r int) {
if l >= r {
return
}
i, j, key := l, r, a[l] //选择第一个数为key
for i < j {
for i < j && a[j] > key { //从右向左找第一个小于key的值
j--
}
if i < j {
a[i] = a[j]
i++
}
for i < j && a[i] < key { //从左向右找第一个大于key的值
i++
}
if i < j {
a[j] = a[i]
j--
}
}
//i == j
a[i] = key
kuai(a, l, i-1)
kuai(a, i+1, r)
}
//归并排序
func guibing(buf []int) {
tmp := make([]int, len(buf))
merge_sort(buf, 0, len(buf)-1, tmp)
}
func merge_sort(a []int, first, last int, tmp []int) {
if first < last {
middle := (first + last) / 2
merge_sort(a, first, middle, tmp) //左半部分排好序
merge_sort(a, middle+1, last, tmp) //右半部分排好序
mergeArray(a, first, middle, last, tmp) //合并左右部分
}
}
func mergeArray(a []int, first, middle, end int, tmp []int) {
// fmt.Printf("mergeArray a: %v, first: %v, middle: %v, end: %v, tmp: %v\n",
// a, first, middle, end, tmp)
i, m, j, n, k := first, middle, middle+1, end, 0
for i <= m && j <= n {
if a[i] <= a[j] {
tmp[k] = a[i]
k++
i++
} else {
tmp[k] = a[j]
k++
j++
}
}
for i <= m {
tmp[k] = a[i]
k++
i++
}
for j <= n {
tmp[k] = a[j]
k++
j++
}
for ii := 0; ii < k; ii++ {
a[first+ii] = tmp[ii]
}
// fmt.Printf("sort: buf: %v\n", a)
}
// 堆排序
func duipai(buf []int) {
temp, n := 0, len(buf)
for i := (n - 1) / 2; i >= 0; i-- {
MinHeapFixdown(buf, i, n)
}
for i := n - 1; i > 0; i-- {
temp = buf[0]
buf[0] = buf[i]
buf[i] = temp
MinHeapFixdown(buf, 0, i)
}
}
func MinHeapFixdown(a []int, i, n int) {
j, temp := 2*i+1, 0
for j < n {
if j+1 < n && a[j+1] < a[j] {
j++
}
if a[i] <= a[j] {
break
}
temp = a[i]
a[i] = a[j]
a[j] = temp
i = j
j = 2*i + 1
}
}
有疑问加站长微信联系(非本文作者)