算法题:
给定一个整型数组,将数组的中的元素按升序排序。
基本思路:
操作:排序
输入:无序整型数组
输出:有序整型数组
这里操作采用堆排序算法,堆排序的基本步骤如下:
- 将整型数组构造成大顶堆结构
- 返回堆顶元素
- 减少堆的长度,有如下情形:
a. 若堆的长度等于0,跳转到第4步
b. 若堆的长度大于0,跳转到第2步 - 返回有序数组
堆排序算法有个关键步骤是构建堆的过程,堆的定义如下:
堆是一个满二叉树,根元素的值大于左右子树所有节点的值,并且左右子树也是一个堆
从堆的定义可以看出,堆的定义是一个递归定义,针对这种递归定义的数据结构,往往会涉及到递归算法。
对于树的构造,一般性的有两种方式,一种是自上而下,另一种是自下而上,至于采用那种方式方便,要依据具体的情况。堆的构造过程是自下而上的方式。这种方式有个好处,每个小堆是否满足堆的性质,只要查看堆顶的元素是否满足堆的性质,如果不满足,可以将根和左右子节点的值进行比较,取得最大的值交换根元素的值,然后继续考虑被交换的位置。这个过程听起来复杂,但是实施起来并不复杂。
常理,到这里就可以进行编码了,但是这里我还是要继续的多讲一些东西。
堆排序算法和其他基本排序算法比起来,它的构造逻辑也是属于简单逻辑,这种逻辑得益于堆的定义,堆是一个满二叉树,也就是说堆可以使用数组进行表示,结点的父子关系可以通过数组的下标运算所得,另外结点之间的关系,可以简化成父节点和左右子节点的关系,父节点的值只要比左右子节点的值大就可以了,而左右子节点所在的左右子树又可以递归的使用这个性质。最重要的是,堆的调整是不需要进行节点调整的(如果你知道红黑树的实现,就可以体会这句话)。
好了,现在我们可以实现堆排序,代码如下:
package main
import "fmt"
// Heap 定义堆排序过程中使用的堆结构
type Heap struct {
arr []int // 用来存储堆的数据
size int // 用来标识堆的大小
}
// adjustHeap 用于调整堆,保持堆的固有性质
func adjustHeap(h Heap, parentNode int) {
leftNode := parentNode*2 + 1
rightNode := parentNode*2 + 2
maxNode := parentNode
if leftNode < h.size && h.arr[maxNode] < h.arr[leftNode] {
maxNode = leftNode
}
if rightNode < h.size && h.arr[maxNode] < h.arr[rightNode] {
maxNode = rightNode
}
if maxNode != parentNode {
h.arr[maxNode], h.arr[parentNode] = h.arr[parentNode], h.arr[maxNode]
adjustHeap(h, maxNode)
}
}
// createHeap 用于构造一个堆
func createHeap(arr []int) (h Heap) {
h.arr = arr
h.size = len(arr)
for i := h.size / 2; i >= 0; i-- {
adjustHeap(h, i)
}
return
}
// heapSort 使用堆对数组进行排序
func heapSort(arr []int) {
h := createHeap(arr)
for h.size > 0 {
// 将最大的数值调整到堆的末尾
h.arr[0], h.arr[h.size-1] = h.arr[h.size-1], h.arr[0]
// 减少堆的长度
h.size--
// 由于堆顶元素改变了,而且堆的大小改变了,需要重新调整堆,维持堆的性质
adjustHeap(h, 0)
}
}
func main() {
// 测试代码
arr := []int{9, 8, 7, 6, 5, 1, 2, 3, 4, 0}
fmt.Println(arr)
heapSort(arr)
fmt.Println(arr)
}
最后说一句,程序员想提升自己的编码能力,不仅需要不停的训练,而且还要多多思考。