Go语言数据结构算法(二十五)堆排序
堆排序算法是一种流行且高效的排序算法.原理是将数组的元素可视化为一种特殊的完全二叉树.称为堆.
1.使用场景:
大型数据集:堆排序相对于大型数据集是有效的.因为其他算法开销对性能影响比较大.
内存分配:堆排序算法是一种就地排序.它不需要额外的内存来保存排序后的元素.
排序优先级队列:堆排序算法通常用于对优先级队列中的元素进行排序.这是一种数据结构.它维护一组元素.每个元素都有一个优先级.
2.实现:
2.1方法:
package data type MaxHeapData struct { slice []int heapSize int } func BuildMaxHeap(slice []int) MaxHeapData { m := MaxHeapData{slice, len(slice)} for i := len(slice) / 2; i >= 0; i-- { m.MaxHeapify(i) } return m } // 创建最大堆对象. func (m MaxHeapData) MaxHeapify(i int) { l, r := 2*i+1, 2*i+2 maxHeap := i if l < m.Size() && m.slice[l] > m.slice[maxHeap] { maxHeap = l } if r < m.Size() && m.slice[r] > m.slice[maxHeap] { maxHeap = r } if maxHeap != i { m.slice[i], m.slice[maxHeap] = m.slice[maxHeap], m.slice[i] m.MaxHeapify(maxHeap) } } func (m MaxHeapData) Size() int { return m.heapSize } // 定义队排序. func HeapSort(slice []int) []int { m := BuildMaxHeap(slice) for i := len(m.slice) - 1; i >= 1; i-- { m.slice[0], m.slice[i] = m.slice[i], m.slice[0] m.heapSize-- m.MaxHeapify(0) } return m.slice }2.2main方法:
func main() { array := []int{33, 23, 56, 7, 8, 18, 99, 28} heapSort := data.HeapSort(array) fmt.Println(heapSort) }3.实战:
3.1方法:
package data type MaxHeapData struct { slice []int heapSize int } func BuildMaxHeap(slice []int) []int { for i := len(slice) / 2; i >= 0; i-- { slice = MaxHeapify(slice, i) } return slice } func MaxHeapify(array []int, i int) []int { l, r := left(i)+1, right(i)+1 maxHeap := i if l < len(array) && l >= 0 && array[l] > array[maxHeap] { maxHeap = l } if r < len(array) && r >= 0 && array[r] > array[maxHeap] { maxHeap = r } if maxHeap != i { array[i], array[maxHeap] = array[maxHeap], array[i] MaxHeapify(array, maxHeap) } return array } func (m MaxHeapData) Size() int { return m.heapSize } // 定义队排序. func HeapSort(slice []int) []int { m := BuildMaxHeap(slice) size := len(m) for i := len(m) - 1; i >= 1; i-- { m[0], m[i] = m[i], m[0] size-- MaxHeapify(m[:size], 0) } return m } func left(i int) int { return 2 * i } func right(i int) int { return 2*i + 1 }3.2main方法:
func main() { array := []int{33, 23, 56, 7, 8, 18, 99, 28} heapSort := data.HeapSort(array) fmt.Println(heapSort) }仰天大笑出门去.
如果大家喜欢我的分享我的话.可以关注我的微信公众号
念何架构之路