[数据结构与算法]Golang 数据结构与算法 —— 堆排序

目录结构

• bucketSort
  – bucketSort.go
  – bucketSort_test.go

bucketSort.go

package heapSort

func heapSort(s []int) {
	heap := make([]int, 0)
	heap = append(heap, 0)
	heap = append(heap, s...)
	step1(heap)
	step2(heap)
	copy(s, heap[1:])
}

// 1 造大顶堆
func step1(heap []int) {
	for i := len(heap) - 1; i > 0; i-- {
		if (i+1)/2 > 0 && heap[i] > heap[(i+1)/2] {
			heap[i], heap[(i+1)/2] = heap[(i+1)/2], heap[i]
		}
	}
}

// 2 堆排序
func step2(heap []int) {
	N := len(heap) //  11
	for i := N - 1; i > 0; i-- {
		heap[1], heap[i] = heap[i], heap[1]
		step1(heap[:i])
	}
}

bucketSort_test.go

package heapSort

import (
	"fmt"
	"math/rand"
	"testing"
)

func BenchmarkHeapSort(b *testing.B) {
	s := make([]int, 0)
	for j := 0; j < 50; j++ {
		j := rand.Intn(1000)
		s = append(s, j)
	}
	b.StartTimer()
	for i := 0; i < b.N; i++ {
		heapSort(s)
	}
	b.StopTimer()
}

测试结果

BenchmarkHeapSort
BenchmarkHeapSort-12    	  972006	      1168 ns/op
PASS