堆排序

2021-04-15 | 129 浏览

堆排序

堆是一种特殊的树形数据结构,其每个节点都有一个值,通常提到的堆都是指一棵完全二叉树,根节点的值小于或者大于两个子结点的值,同时,根节点的两个子树也分别是一个堆

堆排序是一树形选择排序,再排序过程中,将R[1...n]看成是一颗完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子节点之间的内在关系来选择最小的元素

堆一般分为大顶堆和小顶堆i两种不同的类型.对于给定n个记录的序列(r(1),r(2),...r(n)),当且仅当满足条件(r(i)>=r(2i),i=1,2,...,n)时称之为大顶堆,此时堆顶元素比为最大值,对于给定n个记录的序列(r(1),r(2),...,r(n)),当且仅当满足条件(r(i)<=r(2i+1),i=1,2,...,n)时称之为小顶堆,此时,堆顶元素必为最小值

堆排序的思想是对于给定的n个记录,初始时把这些记录看作一棵顺序存储的二叉树,然后将其调整为一个大顶堆,将堆的最后一个元素与堆顶元素(既二叉树的根节点)进行交换后,堆的最后一个元素既为最大记录;接着将前(年)个元素(既不包括最大记录)重新调整为一个大顶堆,再将堆顶元素与当前堆的最后一个元素进行交换后得到次大的记录,重复该过程直到调整的堆中只剩下一个元素时为止,该元素即为最小记录,此时可得到一个有序序列

堆排序主要包括两个过程:一是构建堆; 二是交换堆顶元素与最后一个元素的位置
package main

import "fmt"

func adjustMinHeap(a []int, pos, llen int) {
	var temp int
	child := 0
	for temp = a[pos]; 2*pos+1 <= llen; pos = child {
		child = 2*pos + 1
		if child < llen && a[child] > a[child+1] {
			child++
		}
		if a[child] < temp {
			a[pos] = a[child]
		} else {
			break
		}
	}
	a[pos] = temp
	fmt.Println("排序过程: ", a)
}
func MinHeapSort(array []int) {
	llen := len(array)
	for i := llen/2 - 1; i >= 0; i-- {
		adjustMinHeap(array, i, llen-1)
	}
	for i := llen - 1; i >= 0; i-- {
		tmp := array[0]
		array[0] = array[i]
		array[i] = tmp
		adjustMinHeap(array, 0, i-1)
	}
}

func main() {
	data := []int{6, 4, 9, 8, 7, 6, 0, 3, 2}
	MinHeapSort(data)
	fmt.Printf("排序结果如下:\n")
	fmt.Println(data)
}
程序输出为:
[administrator@administrator-dev 20210414]$ go run 02.go 
排序过程:  [6 4 9 2 7 6 0 3 8]
排序过程:  [6 4 0 2 7 6 9 3 8]
排序过程:  [6 2 0 3 7 6 9 4 8]
排序过程:  [0 2 6 3 7 6 9 4 8]
排序过程:  [2 3 6 4 7 6 9 8 0]
排序过程:  [3 4 6 8 7 6 9 2 0]
排序过程:  [4 7 6 8 9 6 3 2 0]
排序过程:  [6 7 6 8 9 4 3 2 0]
排序过程:  [6 7 9 8 6 4 3 2 0]
排序过程:  [7 8 9 6 6 4 3 2 0]
排序过程:  [8 9 7 6 6 4 3 2 0]
排序过程:  [9 8 7 6 6 4 3 2 0]
排序过程:  [9 8 7 6 6 4 3 2 0]
排序结果如下:
[9 8 7 6 6 4 3 2 0]
堆排序方法对记录较少的文件效果一般,但对于记录较多的文件还是很有效果的,其运行时间主要耗费在创建堆和反复调整堆上.堆排序即使在最坏情况下,其时间复杂度也为O(n*logn)

算法