堆排序算法（HeapSort）

本文主要是介绍堆排序算法（HeapSort），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.堆（heap）

（1）堆的概念
若n个关键字序列$L[\mathrm{1...}n]$满足下面某一条性质，则称为堆（heap）：
1）大根堆：$L(i)>=L(2i)$且$L(i)>=L(2i+1)$ $(1<=i<=n/2)$
2）小根堆：$L(i)<=L(2i)$且$L(i)<=L(2i+1)$ $(1<=i<=n/2)$
说明：可理解为顺序存储的完全二叉树，其每个结点的值大于其左右孩子结点的值

（2）堆的插入
先将新元素放到表尾，与父结点对比，若新元素比父结点更大（小）则将二者互换，若元素互换破坏了上一层级的堆性质，则采用相同的方法继续上调，直到无法上调为止

（3）堆的删除
用表尾的元素代替被删除的元素，若破坏了堆的性质，则与孩子结点中更大（小）的结点互换，若元素互换破坏了下一层级的堆性质，则采用相同的方法继续下调，直到无法下调为止

2.堆排序算法（HeapSort）

（1）堆排序算法思想
每一趟将堆顶元素加入有序子序列（与待排序序列中的最后一个元素交换），并将待排序元素再次调整为大（小）根堆

（2）适用范围
顺序表

2.建立大（小）根堆

把所有非终端结点都检查一遍，是否满足大（小）根堆的要求，如果不满足，则将当前结点与更大（小）的孩子互换，若元素互换破坏了下一层级的堆性质，则采用相同的方法继续向下调整

3.堆排序算法性能分析

性能	性能指标
时间复杂度	$O(n{\log }_{2}n)$
空间复杂度	$O(1)$
稳定性	不稳定

4.堆排序算法代码实现（Java）

public void heapSort(int[] arr, int len){buildMaxHeap(arr, len);for(int i = len ; i > 1 ; i--){int temp = arr[1];arr[1] = arr[i];arr[i] = temp;adjustHead(arr, 1, i-1);}
}public void buildMaxHeap(int[] arr, int len){for(int i = (len - 1) / 2 ; i >= 0 ; i--){adjustHead(arr, i , len);}
}public void adjustHead(int[] arr, int k, int len){arr[0] = arr[k];for(int j = 2 * k ; j <= len ; j *= 2){if(j < len && arr[j] < arr[j+1]){j++;}if(arr[0] > arr[j]){break;}else{arr[k] = arr[j];k = j;}}arr[k] = arr[0];
}

这篇关于堆排序算法（HeapSort）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---