Golang 堆排序与选择排序
Contents
选择排序
select.go，这里以选择最小的为例子
package main
import "fmt"
import "math/rand"
func main() {
var data []int
for i := 0; i < 10000000; i++ {
data = append(data, rand.Int())
}
//fmt.Printf("%v\n", data)
selectSort(data)
fmt.Printf("%v\n", len(data))
}
func selectSort(data []int) {
swapIndex := 0
for i := 0; i < len(data); i++ {
index, _ := min(data, swapIndex)
//fmt.Printf("min index = %v, i = %v\n", index, i)
swap(data, swapIndex, index)
swapIndex++
}
}
func swap(data []int, src int, dest int) {
data[src], data[dest] = data[dest], data[src]
//fmt.Printf("after swap => %v\n", data)
}
func min(data []int, startIndex int) (index int, d int) {
d = data[startIndex]
index = startIndex
for i := startIndex + 1; i < len(data); i++ {
next := data[i]
if next < d {
d = next
index = i
}
}
return
}
堆排序
heapSort.go
package main
import "math/rand"
import "fmt"
func main() {
var data []int
for i := 0; i < 25; i++ {
data = append(data, rand.Intn(100))
}
HeapSort(data)
fmt.Printf("final value = %v\n", data)
}
// HeapSort : 堆排序
func HeapSort(data []int) {
if len(data) <= 1 {
return
}
maxIndex := len(data) - 1
buildAllMaxHeap(data)
for i := len(data) - 1; i >= 0; i-- {
data[0], data[maxIndex] = data[maxIndex], data[0]
localMaxHeap(data[:maxIndex], 0)
maxIndex--
}
}
//全局创建最大堆
func buildAllMaxHeap(data []int) {
//从最后一颗树的根节点开始处理
for i := (len(data) - 1) / 2; i >= 0; i-- {
localMaxHeap(data, i)
}
}
//每一颗小树中，要保持最大堆
func localMaxHeap(data []int, root int) {
left := getLeft(root)
right := getRight(root)
biggest := root
if left < len(data) && data[left] > data[biggest] {
biggest = left
}
if right < len(data) && data[right] > data[biggest] {
biggest = right
}
if biggest != root {
data[root], data[biggest] = data[biggest], data[root]
localMaxHeap(data, biggest)
}
}
// 获取元素的左节点
func getLeft(index int) int {
left := 2*index + 1
return left
}
// 获取元素的右节点
func getRight(index int) int {
right := 2 * (index + 1)
return right
}
// 获取元素的父节点
func getParentIndex(index int) int {
if index == 0 {
return index
}
if index%2 == 0 {
return index/2 - 1
}
return index / 2
}