PS：本文为转载文章，原文的可读性会更好，文末有原文链接目录1，堆排序1、1BigTopHeap1,2SmallTopHeap1,3HeapSortSpeedtest1,heapsorting1,1bigtopheapsorting是利用堆的数据结构设计的一种排序算法，堆排序是一种选择排序，其worst，best，平均时间复杂度都是O(nlogn)，也是不稳定排序；大顶堆是一棵完全二叉树，具有如下性质，即每个节点的值都大于等于其左右子节点的值，但我们并不要求该节点左边的值child跟右孩子的值的大小有什么关系。好吧，我们举个例子来解释一下大顶堆。先画一张图，如下图1所示：图片注：图1中白色数字表示节点的值，蓝色数字表示节点的编号。我们按层对图1中的堆进行编号，到数组的映射是这样排序的：arr={9,7,8,3,4,5,6,1,2}。这时候我们发现，图1中节点号和数组arr的下标是一一对应的，满足arr[i]>=arr[2i+1]&&arr[的条件i]>=arr[2i+2]为真；一般使用large堆顶升序排序。好吧，说一下从无序二叉树形成大顶堆的基本思路：(1)构造待排序的序列进入大顶堆。(2)此时，整个序列的最大值就是堆顶的根节点。(3)与end元素交换，end为此时的最大值。(4)然后将剩下的n-1个元素重新构造成堆，这样就会得到n个元素的第二小的值；如此反复执行，就可以得到一个有序的序列。看完了二叉树形成大顶堆的基本思想，可能有人会说还是不懂，好吧，我们现在举个例子：（1）假设我们有一棵无序二叉树，如图在图2中。2中的二叉树被映射成这样的数组：arr={1,3,4,2,5};注：白色数字代表节点的值，蓝色数字代表节点的编号，如下图所示。图(2)我们从第一个非叶子节点开始，从下到上，从左到右，计算公式：arr.length/2-1=5/2-1=1，从1个数开始，即为3个节点，右子节点5在以3节点为父节点的二叉子树（3节点、2节点、5节点）中最大，所以交换3节点和5节点的位置，二叉树图3中的得到，图3中的二叉树被映射成这样的数组：arr={1,5,4,2,3};图（3）图2中的二叉树，3个节点所在的层，从左到右，右边的节点（4个节点）没有子节点，所以4个节点不需要排成一个大的顶堆;从下往上，找到图3中二叉树的第一个非叶子节点（是5个节点，图2中第一个非叶子节点是3个节点），即节点1，右子节点以节点1为父节点的二叉子树（节点1，节点5，节点4）中的5最大，所以节点5和节点1交换位置，得到如图4所示的二叉树。图4中的二叉树被映射成这样的数组：arr={5,1,4,2,3};图（4）此时根节点为父节点的大顶堆已经排好，即第一层的大顶堆已经排好；但是第二层的大顶堆还没有排好，也就是根节点的左子节点1的大顶堆还没有排序，所以图4中二叉树的右子节点以1个节点为父节点（1节点、2节点、3节点）最大，因此交换1节点和3节点的位置，得到图5中的二叉树。5的二叉树映射的数组是这样的：arr={5,3,4,2,1};图片在这里，图5中的二叉树排列成一个大顶堆，满足条件：父节点总是比子节点的值大；参见图2，这里是从第三层开始比较，即从叶子节点开始比较，比如以3个节点为父节点形成的子树（3个节点，2个节点，5个节点），首先找到较大的值（5个节点）和“top”到父节点，然后比较第二层的节点，把第二层中较大的值“top”到父节点，最后最大值一定是3比根节点“顶”，所以根节点的值最大；大顶堆的排列规则无非就是先排列根节点的大顶堆，再排列根节点的子节点的大顶堆，再排列根节点的子节点的大顶堆根节点。节点的子节点的大顶堆...，以此类推，最后排叶子节点的父节点的大顶堆，最后将这棵二叉树排成一个大顶堆。好了，说了这么多，我们这里用代码来实现一下：将图2中的二叉树排列成一个大顶堆。公共类HeapSort{publicstaticvoidmain(String[]args){int[]arr={1,3,4,2,5};HeapSorths=newHeapSort();hs.sort(arr);for(inti=0;i
