손 훑 기 golang 기본 데이터 구조 와 알고리즘 더미 정렬
최근 에 < > ([일] 석 다 보 휘, 미 야자 키 수 일) 시 리 즈 를 읽 고 골 랑 으로 연습 할 예정 입 니 다.
더미 정렬
。
, , 。
, 。
n , O(nlogn)。
O(logn)。
n , O(nlog n)。
, O(nlog n)。
, 、 、 O(n^2) 。
<> 【 】 ;
목표.
설계 하 다.
유닛 테스트
heap_sort_test. go, 테스트 과정 은 이전의 거품, 선택, 삽입 등 과 유사 하지만 테스트 배열 은 10 만 요소 로 확대 되 었 습 니 다.
package sorting
import (
"fmt"
"learning/gooop/sorting"
"learning/gooop/sorting/heap_sort"
"math/rand"
"testing"
"time"
)
func Test_HeapSort(t *testing.T) {
fnAssertTrue := func(b bool, msg string) {
if !b {
t.Fatal(msg)
}
}
reversed := false
fnCompare := func(a interface{}, b interface{}) sorting.CompareResult {
i1 := a.(int)
i2 := b.(int)
if i1 < i2 {
if reversed {
return sorting.GREATER
} else {
return sorting.LESS
}
} else if i1 == i2 {
return sorting.EQUAL
} else {
if reversed {
return sorting.LESS
} else {
return sorting.GREATER
}
}
}
fnTestSorter := func(sorter sorting.ISorter) {
reversed = false
// test simple array
samples := []interface{} { 2,3,1,5,4,7,6 }
sorter.Sort(samples, fnCompare)
fnAssertTrue(fmt.Sprintf("%v", samples) == "[1 2 3 4 5 6 7]", "expecting 1,2,3,4,5,6,7")
t.Log("pass sorting [2 3 1 5 4 7 6] >> [1 2 3 4 5 6 7]")
// test 10000 items sorting
rnd := rand.New(rand.NewSource(time.Now().UnixNano()))
sampleCount := 100*1000
t.Logf("prepare large array with %v items", sampleCount)
samples = make([]interface{}, sampleCount)
for i := 0;i < sampleCount;i++ {
samples[i] = rnd.Intn(sampleCount*10)
}
t.Logf("sorting large array with %v items", sampleCount)
t0 := time.Now().UnixNano()
sorter.Sort(samples, fnCompare)
cost := time.Now().UnixNano() - t0
for i := 1;i < sampleCount;i++ {
fnAssertTrue(fnCompare(samples[i-1], samples[i]) != sorting.GREATER, "expecting <=")
}
t.Logf("end sorting large array, cost = %v ms", cost / 1000000)
// test 0-20
sampleCount = 20
t.Log("sorting 0-20")
samples = make([]interface{}, sampleCount)
for i := 0;i < sampleCount;i++ {
for {
p := rnd.Intn(sampleCount)
if samples[p] == nil {
samples[p] = i
break
}
}
}
t.Logf("unsort = %v", samples)
sorter.Sort(samples, fnCompare)
t.Logf("sorted = %v", samples)
fnAssertTrue(fmt.Sprintf("%v", samples) == "[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19]", "expecting 0-20")
t.Log("pass sorting 0-20")
// test special
samples = []interface{} {}
sorter.Sort(samples, fnCompare)
t.Log("pass sorting []")
samples = []interface{} { 1 }
sorter.Sort(samples, fnCompare)
t.Log("pass sorting [1]")
samples = []interface{} { 3,1 }
sorter.Sort(samples, fnCompare)
fnAssertTrue(fmt.Sprintf("%v", samples) == "[1 3]", "expecting 1,3")
t.Log("pass sorting [1 3]")
reversed = true
samples = []interface{} { 2, 3,1 }
sorter.Sort(samples, fnCompare)
fnAssertTrue(fmt.Sprintf("%v", samples) == "[3 2 1]", "expecting 3,2,1")
t.Log("pass sorting [3 2 1]")
}
t.Log("
testing HeapSort")
fnTestSorter(heap_sort.HeapSort)
}
테스트 출력
10 만 요소 의 정렬 은 수 십 밀리초 밖 에 걸 리 지 않 습 니 다. 거품, 선택, 삽입 등 정렬 보다 지수 급 이 높 아 집 니 다. 대 가 는 한 무더기 의 공간 을 더 차지 하 는 것 입 니 다.
$ go test -v heap_sort_test.go
=== RUN Test_HeapSort
heap_sort_test.go:109:
testing HeapSort
heap_sort_test.go:48: pass sorting [2 3 1 5 4 7 6] >> [1 2 3 4 5 6 7]
heap_sort_test.go:53: prepare large array with 100000 items
heap_sort_test.go:59: sorting large array with 100000 items
heap_sort_test.go:66: end sorting large array, cost = 67 ms
heap_sort_test.go:70: sorting 0-20
heap_sort_test.go:81: unsort = [4 15 1 13 19 14 11 12 9 8 3 7 16 18 2 10 17 6 0 5]
heap_sort_test.go:84: sorted = [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19]
heap_sort_test.go:86: pass sorting 0-20
heap_sort_test.go:91: pass sorting []
heap_sort_test.go:95: pass sorting [1]
heap_sort_test.go:100: pass sorting [1 3]
heap_sort_test.go:106: pass sorting [3 2 1]
--- PASS: Test_HeapSort (0.07s)
PASS
ok command-line-arguments 0.076s
IHeap.go
정의 더미 인터페이스
package heap_sort
type IHeap interface {
Size() int
IsEmpty() bool
IsNotEmpty() bool
Push(value interface{})
Pop() (error, interface{})
}
tArrayHeap
package heap_sort
import (
"errors"
"learning/gooop/sorting"
)
type tArrayHeap struct {
comparator sorting.CompareFunction
items []interface{}
size int
version int64
}
func newArrayHeap(comparator sorting.CompareFunction) IHeap {
return &tArrayHeap{
comparator: comparator,
items: make([]interface{}, 0),
size: 0,
version: 0,
}
}
func (me *tArrayHeap) Size() int {
return me.size
}
func (me *tArrayHeap) IsEmpty() bool {
return me.size <= 0
}
func (me *tArrayHeap) IsNotEmpty() bool {
return !me.IsEmpty()
}
func (me *tArrayHeap) Push(value interface{}) {
me.version++
me.ensureSize(me.size + 1)
me.items[me.size] = value
me.size++
me.shiftUp(me.size - 1)
me.version++
}
func (me *tArrayHeap) ensureSize(size int) {
for ;len(me.items) < size; {
me.items = append(me.items, nil)
}
}
func (me *tArrayHeap) parentOf(i int) int {
return (i - 1) / 2
}
func (me *tArrayHeap) leftChildOf(i int) int {
return i*2 + 1
}
func (me *tArrayHeap) rightChildOf(i int) int {
return me.leftChildOf(i) + 1
}
func (me *tArrayHeap) last() (i int, v interface{}) {
if me.IsEmpty() {
return -1, nil
}
i = me.size - 1
v = me.items[i]
return i,v
}
func (me *tArrayHeap) shiftUp(i int) {
if i <= 0 {
return
}
v := me.items[i]
pi := me.parentOf(i)
pv := me.items[pi]
if me.comparator(v, pv) == sorting.LESS {
me.items[pi], me.items[i] = v, pv
me.shiftUp(pi)
}
}
func (me *tArrayHeap) Pop() (error, interface{}) {
if me.IsEmpty() {
return gNoMoreElementsError, nil
}
me.version++
top := me.items[0]
li, lv := me.last()
me.items[0] = nil
me.size--
if me.IsEmpty() {
return nil, top
}
me.items[0] = lv
me.items[li] = nil
me.shiftDown(0)
me.version++
return nil, top
}
func (me *tArrayHeap) shiftDown(i int) {
pv := me.items[i]
ok, ci, cv := me.minChildOf(i)
if ok && me.comparator(cv, pv) == sorting.LESS {
me.items[i], me.items[ci] = cv, pv
me.shiftDown(ci)
}
}
func (me *tArrayHeap) minChildOf(p int) (ok bool, i int, v interface{}) {
li := me.leftChildOf(p)
if li >= me.size {
return false, 0, nil
}
lv := me.items[li]
ri := me.rightChildOf(p)
if ri >= me.size {
return true, li, lv
}
rv := me.items[ri]
if me.comparator(lv, rv) == sorting.LESS {
return true, li, lv
} else {
return true, ri, rv
}
}
var gNoMoreElementsError = errors.New("no more elements")
ISorter
package sorting
type ISorter interface {
Sort(data []interface{}, comparator CompareFunction) []interface{}
}
type CompareFunction func(a interface{}, b interface{}) CompareResult
type CompareResult int
const LESS CompareResult = -1
const EQUAL CompareResult = 0
const GREATER CompareResult = 1
tHeapSort
package heap_sort
import "learning/gooop/sorting"
type tHeapSort struct {
}
func newHeapSort() sorting.ISorter {
return &tHeapSort{}
}
func (me *tHeapSort) Sort(data []interface{}, comparator sorting.CompareFunction) []interface{} {
heap := newArrayHeap(comparator)
for _,it := range data {
heap.Push(it)
}
for i,_ := range data {
e,v := heap.Pop()
if e == nil {
data[i] = v
} else {
panic(e)
}
}
return data
}
var HeapSort = newHeapSort()
(end)
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.