首页 > 代码库 > 排序算法（五）
排序算法（五）
2. 选择排序—堆排序（Heap Sort）
堆排序是一种树形选择排序，是对直接选择排序的有效改进。
基本思想：
堆的定义如下：具有n个元素的序列（k1,k2,...,kn），当且仅当满足
时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素）为最小项（小顶堆）。
若以一维数组存储一个堆，则堆对应一颗完全二叉树，且所有非叶节点的值均不大于（或不小于）其子女的值，根节点的值（堆顶元素）的值是最小（或最大）的。如：
（a）大堆顶序列（96,83,27,38,11,09）
（b）小堆顶序列（12,36,24，85,47,30,53,91）
初始时把要排列的的n个数的序列看做是一颗顺序存储的二叉树（一维数组存储二叉树），调整他们的存储序，使之成为一个堆。将堆顶元素输出，得到n个元素中最小（或最大）的元素，这时堆的根节点的数最小（或最大）。然后对前面的n-1个元素重新调整使之成为堆，输出堆顶元素，得到n个元素中次小（或次大）的元素。依此类推，知道只有俩个节点的堆，并对他们做交换，最后得到n个节点的有序序列，称这个过程为堆排序。
因此，实现堆排序需要解决俩个问题：
1、如何将n个待排序的数建成堆。
2、输出堆顶元素后，怎样调整剩余n-1个元素，使其成为堆。
首先，我们讨论第二个问题：输出堆顶元素后，对剩余的n-1个元素重新建成堆的调整过程。
调整小堆顶的方法（大堆顶也是一样的道理）：
1、设有m个元素的堆，输出堆顶元素后，剩下m-1个元素。将堆底元素送入堆顶（最后一个元素与堆顶元素进行交换），堆被破坏，其原因仅是根节点不满足堆的性质。
2、将目前最新的根节点与左、右子数中较小元素进行交换。
3、若与左子数交换：如果左子数堆被破坏，即左子数的根节点不满足堆的性质，则重复方法（2）。
4、若与右子数交换，如果右子数堆被破坏，即右子数的根节点不满足堆的性质。则重复方法（2）。
5、继续对不满足堆性质的子数进行上述交换操作，知道叶子节点，堆被建成。
称这个字根节点到叶子节点的调整过程称为筛选。如图：
再讨论对n个元素初始建堆的过程。
建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。
1、n个节点的完全二叉树，则最后一个节点是n/2个节点的子数。
2、筛选从第n/2个节点为根的子数开始，该子数成为堆。
3、之后向前一次对各节点为根的子数进行筛选，使之成为堆，直到根节点。
如图建堆的初始过程：无序序列：（49，38，65，97，76，13，27，49）
算法的实现：
从算法的描述来看，堆排序需要俩个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以，堆排序有俩个函数组成，一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。
public class HeapSort { public static void main(String[] args) { int[] a = {12,54,76,23,435,98,21,1,2,23,54,76,34,2,78,243}; heapSort(a, a.length); for(int i=0; i<a.length; i++){ System.out.print(a[i]+" "); } } /** * 堆排序算法 * */ public static void heapSort(int[] a,int length){ buildingHeap(a, a.length); //初始堆 for(int i=length-1; i>0; --i){ int temp = a[i]; a[i] = a[0]; a[0] = temp; heapAdjust(a, 0, i); } } /** * 初始堆进行调整 * 将a[0..length-1]建成堆 * 调整完之后第一个元素师序列的最小元素 * */ public static void buildingHeap(int[] a,int length){ //最后一个有孩子的节点的位置i = length/2 - 1 for(int i=(length/2)-1; i>=0; --i){ heapAdjust(a, i, length); } } /** * 已知a[a...m]除了a[s]外均满足堆的定义 * 调整a[s],使其成为大顶堆，即将对第s个节点为根的子数帅选 * * @param a是待调整的数组 * @param s是待调整的数组元素的位置 * @param length是数组的长度 * */ public static void heapAdjust(int[] a,int s,int length){ int temp = a[s]; int child = 2*s+1; //左孩子节点的位置。 while(child < length){ if(child+1 < length && a[child] <a[child+1] ){//如果右孩子大于左孩子（找到比当前待调整节点大的孩子） ++ child; } if(a[s]<a[child]){//如果较大的子节点大于父节点 a[s] = a[child];//那么把较大的子节点往上移动，替换他的父节点 s = child; //重新设置s,即待调整的下一个节点的位置 child = 2*s+1; }else{ //如果当前待调整节点大于他的左右孩子，则不需要调整，直接退出 break; } a[s] = temp;//当前待调整的节点放到比其大的孩子的节点的位置上 } }}
算法分析：
设数深度为k，k=log2n+1。从根到叶的筛选，元素比较次数之多2（k-1）次，交换记录之多k次。所以，在建好堆后，排序过程中的次数不超过下式：
而建堆的比较次数不超过4n次，因此堆排序最坏情况下，时间复杂度也为：O（nlogn）。
排序算法（五）