Go实现堆排序

这次用Golang写了堆排序,Go的unsafe包蛮好用的嘛^_^


type Node interface {
    /*
    return the value < i
     */
    Comparable(i Node) int
}

func HeapSort(a []Node) {
    N := len(a) - 1
    for k := N / 2; k >= 1; k-- {
        sink(a, k, N)
    }
    for N > 1 {
        exch(a, 1, N)
        N--
        sink(a, 1, N)
    }

}
func less(i, j Node) int {
    return i.Comparable(j)
}
func sink(a[]Node, k, l int) {
    for (k * 2 <= l) {
        j := k * 2
        if j < l && less(a[j], a[j + 1]) < 0 {
            j++
        }
        if less(a[k], a[j]) >= 0 {
            break
        }
        exch(a, k, j)
        k = j
    }
}
func exch(a []Node, i, j int) {
    a[i], a[j] = a[j], a[i]
}

type Int int

func (v Int)Comparable(i Node) int {
    s := v - i.(Int)
    return *(*int)(unsafe.Pointer(&s))
}
func isSorted(a []Node) {
    for i := 1; i < len(a) - 1; i++ {
        if (a[i].Comparable(a[i + 1]) > 0) {
            fmt.Println("is not sorted")
            return
        }
    }
    fmt.Println("is sorted")
}

func main() {
    d := make([]Node, 1, 2000)
    for i := 0; i < 500; i++ {
        s := rand.Int() % 500
        v := (*Int)(unsafe.Pointer(&s))
        d = append(d, *v)
    }
    isSorted(d)
    heapSort(d)
    isSorted(d)
}
文章目录