基于空接口的go语言归并排序mergSort

Beginner18 · · 667 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。


//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)
}

 


有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

667 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传