Rumah >masalah biasa >堆排序是一种什么排序
堆排序是一种将无序的序列生成一个最大堆,将堆顶元素与最后一个元素对换位置,并将剩下元素生成最大堆,依次进行元素交换并生成最大堆的排序。
堆排序
将无序的序列生成一个最大堆,将堆顶元素与最后一个元素对换位置,将剩下元素生成最大堆,依次进行元素交换并生成最大堆
时间复杂度:O(NlogN) 空间复杂度:O(1)
简介:
堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
堆的操作
在堆的数据结构中,堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。
堆中定义以下几种操作:
最大堆调整(Max Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点
创建最大堆(Build Max Heap):将堆中的所有数据重新排序
堆排序(HeapSort):移除位在第一个数据的根节点,并做最大堆调整的递归运算
Atas ialah kandungan terperinci 堆排序是一种什么排序. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!