//merge sort: int float32 float64
//1 divide: 中分,仅存在一个变量时不分
//2 merge: 合并子列,若一个子列为空则
//直接复制另外一个子列
//fileName: mergeSort.go
package mySort1
import (
//"fmt"
"log"
)
//利用空接口实现任意类型,空接口类型不存在比较
//比较需利用a.(int)将空接口类型断言为具体类型
//通过a.(type)可以判断空接口的实际类型
func MergeSort(arr []interface{}, low, high int) {
desArr := make([]interface{}, high+1)
if len(desArr) < 1 {
log.Panicln(" short of memory")
}
mergeSort(arr, desArr, low, high)
}
func mergeSort(arr, desArr []interface{}, low, high int) {
if len(arr) < 1 || len(desArr) < 1 || high > (len(arr)-1) || len(desArr) < len(arr) || (low > high) {
log.Fatalf("func mergeSort: input error\n")
}
i, j := low, high
if low < high {
mid := (i + j) / 2
mergeSort(arr, desArr, i, mid)
mergeSort(arr, desArr, mid+1, j)
merge(arr, desArr, i, mid, mid+1, j)
}
}
func merge(arr, desArr []interface{}, lowleft, highleft, lowright, highright int) {
i1, j1, i2, j2 := lowleft, highleft, lowright, highright
if len(arr) < 1 || len(desArr) < 1 || highright > (len(arr)-1) ||
len(desArr) < len(arr) || (highleft > lowright) ||
(lowleft > highleft) || (lowright > highright) {
log.Fatalf("func merge: input error \n")
}
len := (j1 - i1) + (j2 - i2) + 2
var num int = 0
//merge
for {
if i1 > j1 || i2 > j2 {
break
}
//判定待排序数组类型
//待排序数组转为相应类型并比较
//空接口无比较
if compare(arr[i1], arr[i2]) {
desArr[num] = arr[i1]
i1++
num++
} else {
desArr[num] = arr[i2]
i2++
num++
}
}
//copy
if i1 <= j1 {
copy(desArr[num:len], arr[i1:(j1+1)])
}
if i2 <= j2 {
copy(desArr[num:len], arr[i2:(j2+1)])
}
//copy destArr to arr
copy(arr[lowleft:(highright+1)], desArr[0:len])
}
//基于空接口的比较函数:目前适用于int float32 float64用户可自行加入其他数据类型
//比较空接口参数大小
//用于mergeSort及其他排序算法
//fileName: compare.go
package mySort1
import (
"log"
)
func compare(left, right interface{}) bool {
switch left.(type) {
//待排序数组转为相应类型并比较
//空接口无比较
case int:
//接口类型断言
if left.(int) < right.(int) {
return true
} else {
return false
}
case float32:
if left.(float32) < right.(float32) {
return true
} else {
return false
}
case float64:
if left.(float64) < right.(float64) {
return true
} else {
return false
}
default:
log.Panicln("ilegal type: int float32 float64")
}
return false
}
//归并排序用法示例
//mergeSort用法示例
//fileName: test.go
package main
import (
"fmt"
"mySort1"
)
func main() {
//定义空接口数组
var arr = make([]interface{}, 6)
//待排序数组
arr1 := []float32{4.1, 5.3, 8, 1, 3, 2}
//空接口数组赋值
for i, _ := range arr {
arr[i] = arr1[i]
}
fmt.Println("before: ", arr)
mySort1.MergeSort(arr, 0, len(arr)-1)
fmt.Println("after: ", arr)
}
有疑问加站长微信联系(非本文作者)