go语言中实现堆排序算法代码示例

Go  /  管理员 发布于 3年前   455

堆排序算法将未排序的数据划分为已排序和未排序区域，并通过提取最大元素并将其移动到已排序区域来迭代地缩小未排序区域。

堆排序算法：

http://en.wikipedia.org/wiki/Heapsort

下面是一个在Go语言中实现堆排序算法的示例：

 package main

 import (
 	"fmt"
 )

 func maxHeapify(tosort []int, position int) {
 	size := len(tosort)
 	maximum := position
 	leftChild := 2*position + 1
 	rightChild := leftChild + 1
 	if leftChild < size && tosort[leftChild] > tosort[position] {
 		maximum = leftChild
 	}
 	if rightChild < size && tosort[rightChild] > tosort[maximum] {
 		maximum = rightChild
 	}

 	if position != maximum {
 		tosort[position], tosort[maximum] = tosort[maximum], tosort[position]
 		maxHeapify(tosort, maximum) //recursive
 	}
 }

 func buildMaxHeap(tosort []int) {

 	// 来自http://en.wikipedia.org/wiki/Heapsort
 	// iParent = floor((i-1) / 2)

 	for i := (len(tosort) - 1) / 2; i >= 0; i-- {
 		maxHeapify(tosort, i)
 	}
 }

 func heapSort(tosort []int) {
 	buildMaxHeap(tosort)
 	for i := len(tosort) - 1; i >= 1; i-- {
 		tosort[i], tosort[0] = tosort[0], tosort[i]
 		maxHeapify(tosort[:i-1], 0)
 	}
 }

 func main() {
 	unsorted := []int{99, 55, 33, 67, 9, 5, 431, 999, 8108, 108}
 	fmt.Println("原数据 : ", unsorted)

 	heapSort(unsorted)
 	fmt.Println("排序后数据 : ", unsorted)
 }

效果：

原数据：[99 55 33 67 9 5 431 999 8108 108]
排序后数据：[9 5 33 55 67 99 108 431 999 8108]