系列文章目录
文章目录
- 系列文章目录
- 前言
- 一、堆排序定义
- 二、时间复杂度
- 三、实现思路
- a.注意（升/降）
- 四、topk问题
前言
常见的基本排序算法有冒泡、选择、插入，但效率太低。
堆排序和快速排序算法则是相对高效的算法。这篇主要先介绍堆排序
一、堆排序定义
堆排序就是借助（大/小）堆的特性，实现的快速排序
二、时间复杂度
时间复杂度：N * log2
本质就是建堆后，借助堆来调整N个数的位置，每次调整时间为堆高度log2
三、实现思路
（以小堆为例）
- 先将数据建小堆，此时堆顶是最小值。
- 将堆顶元素与数组末尾的元素交换，此时最小值被放到数组末尾。
- 将堆的有效长度-1，末尾元素视为已排序，不参与后续调整。
- 对堆顶的元素进行向下调整，使其重新满足小堆的特性
- 重复上述过程，直到堆的有效长度为1
//实现堆排序————时间复杂度：N * logN (一次向下调整是N, 执行N次)voidHeapSort(int*a,intn){//1、建堆for(inti=(n-1-1)/2;i>=0;i--)//需要从最后一个节点的父亲节点,开始向下调整{AdjustDown(a,n,i);}//2、将排序好的最小值，排出堆排序的范围intend=n-1;//3、再一直对根节点实现向下调整while(end>0){swap(&a[0],&a[end]);//再次选择最小的值AdjustDown(a,end,0);end--;}}至此，实现了数组的降序排列
a.注意（升/降）
排升序，建大堆
排降序，建小堆
因为每次堆顶会和数组末尾的元素交换
四、topk问题
N个数中找出最大或最小的前K个数？
最优方案：建立一个K的数的堆。
如果想找K个最大数就建小堆，想找K个最小数就建大堆
（以小堆为例）
遍历N-K个数，凡是比堆顶大的数就替换堆顶数据，进堆向下调整。
（因为堆顶的数总是较小的）最后剩下的k个数就是前K个最大的数。
前K个最小的数同理可得。