n*log(3)n排序算法

大佬教程收集整理的这篇文章主要介绍了n*log(3)n排序算法，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

老规矩，上来先表示对原作者的敬重之心：n*log(3)n排序算法 -- 修江的芦苇

关于三叉堆排序呢，对于已经理解了二叉堆排序的人来说，其实很容易理解。该讲的在原作里面，作者已经讲的很清楚了，这里就只贴一下代码了。

首先是 heap.go:

package heap // import "triple-heap"

import "sort"

type interfacE interface {
	sort.Interface
	Push(x interface{})
	Pop() interface{}
}

func Init(h InterfacE) {
	n := h.Len()
	for i := n/3 - 1; i >= 0; i-- {
		down(h,i,n)
	}
}

func Push(h Interface,x interface{}) {
	h.Push(X)
	up(h,h.Len()-1)
}

func Pop(h InterfacE) interface{} {
	n := h.Len() - 1
	h.Swap(0,n)
	down(h,n)
	return h.Pop()
}

func Remove(h Interface,i int) interface{} {
	n := h.Len() - 1
	if n != i {
		h.Swap(i,n)
		down(h,n)
		up(h,i)
	}
	return h.Pop()
}

func Fix(h Interface,i int) {
	down(h,h.Len())
	up(h,i)
}

func up(h Interface,j int) {
	for {
		i := (j - 1) / 3 // parent
		if i == j || !h.Less(j,i) {
			break
		}
		h.Swap(i,j)
		j = i
	}
}

func down(h Interface,n int) {
	for {
		j1 := 3*i + 1
		if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
			break
		}
		j := j1 // left child
		if j2 := j1 + 1; j2 < n && !h.Less(j,j2) {
			j = j2 // = 3*i + 2  // mid child
		}
		if j3 := j1 + 2; j3 < n && !h.Less(j,j3) {
			j = j3 // = 3*i + 3  // right child
		}
		if !h.Less(j,j)
		i = j
	}
}

接下来是 sort.go:

package main

import (
	"fmt"
	"triple-heap"
)

type myHeap []int

func (h *myHeap) Less(i,j int) bool {
	return (*h)[i] < (*h)[j]
}

func (h *myHeap) Swap(i,j int) {
	(*h)[i],(*h)[j] = (*h)[j],(*h)[i]
}

func (h *myHeap) Len() int {
	return len(*h)
}

func (h *myHeap) Pop() (v interface{}) {
	*h,v = (*h)[:h.Len()-1],(*h)[h.Len()-1]
	return
}

func (h *myHeap) Push(v interface{}) {
	*h = append(*h,v.(int))
}

func TripleHeapSort(h heap.InterfacE) {
	heap.Init(h)
	var t = make([]interface{},h.Len())
	for h.Len() > 0 {
		t = append(t,heap.pop(h))
	}
	for i := 0; i < len(t); i++ {
		h.Push(t[i])
	}
}

func main() {
	var h = myHeap{5,3,1,9,6,4,7,8,2}
	fmt.Println(h)
	TripleHeapSort(&h)
	fmt.Println(h)
}

运行 go run sort.go结果:

[5 3 1 9 0 6 4 7 8 2]
[0 1 2 3 4 5 6 7 8 9]

对于包的组织和管理，大家自己去搞咯~

好啦，本期节目到此为止，咱们下期再见！

大佬总结

以上是大佬教程为你收集整理的n*log(3)n排序算法全部内容，希望文章能够帮你解决n*log(3)n排序算法所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。