首页 > 代码库 > 堆排序
堆排序
上一篇完成了堆的建立。在此基础上就可以实现堆排序。
思路：在此我们以实现从小到大排序为例。通过第一次的堆建立，生成的大顶堆的根结点值是最大值。然后我们将这个值放到某个地方可以不管它了（实际操作时都是放到整个堆的最后面，然后把最后面那个结点值放到最顶端），此时我们需要操作的元素个数已经少了一个，把剩下的元素再做一个建堆的操作（其实就是堆顶根结点元素的一个交换排列，其他节点的元素是之前已经排列好了的）。依次这个流程到最后。
注意：如果要做一个从大到小的排序，那么需要建立一个小顶堆，即最上面的元素是最小的。然后再堆排序的过程中会把最小的元素放到最后面，这样就实现了一个从大到小的排序。反之，从小到大排序，也是一样的道理。
下面看java实现的代码。综合了堆建立的代码。
package test;/** * @author hushunfeng * * 大顶堆堆排序 * 从小到大排序 * */public class HeapSort { public static void main(String[] args) { int[] array = {10,20,30,40,50,60,70,80}; //调整堆 int temp = 0; for(int j=7;j>=0;j--) { createHeap(array,j+1); temp = array[0]; array[0] = array[j]; array[j] = temp; } for(int i=0;i<8;i++) { System.out.println(array[i]); } } /** * 将无序序列进行建堆 * @param array 要建的堆 */private static void createHeap(int[] array,int heapNum) { //heapNum = array.length; //根据建堆过程，先从第n/2个元素开始 //它是最后一个非终端结点 for(int i = heapNum/2-1; i >= 0; i--) { adjustNode(array,i,heapNum); } } /** * * 将parentNode为根结点的子树调整成一个最大堆 * @param array 要调整的无序序列，以数组的形式进行存储 * @param parentNode 以此结点为根结点建立子树 * */ //由于我们采用的是大顶堆,父结点要调整成大于子结点 private static void adjustNode(int[] array,int parentNode,int nodeNum) { //数组长度 // int arrayNum = array.length; //跳动的父结点游标(在子树层数大于2层时适用) int parentIndex = parentNode; //左子结点 int childLeftNode = 2*parentIndex+1; //右子结点 int childRightNode = 2*parentIndex+2; // int maxNode; //将可能要跳动的父结点的数据缓存起来 int temp = array[parentNode]; //不断地跳动父结点的游标 //防止右子结点不存在这种情况，不然会内存溢出 while(childLeftNode<nodeNum) { //此种情况下已经不存在右结点了 if(childLeftNode==nodeNum-1) { maxNode = childLeftNode; } else { //先比较左右子结点 if(array[childLeftNode]>array[childRightNode]) maxNode = childLeftNode; else maxNode = childRightNode; } //比较，交换位置 if(array[parentIndex]<array[maxNode]) { //将较大的子结点交换到父结点的位置 array[parentIndex] = array[maxNode]; array[maxNode] = temp; //往下移一层，再进行一次比较交换操作 //原先的子结点现在变成了父结点 parentIndex = maxNode; //下一层的子结点 childLeftNode = 2*parentIndex+1; childRightNode = 2*parentIndex+2; } //如果判断出父结点为最大，直接跳出循环 //无需再做交换动作，因为下面的元素都已经排成了大堆 else break; } } }
注：相比堆建立中，程序稍微进行了优化和修改。
修改后的第二版，考虑到从第二次建堆开始只需对根结点进行调整。
package test;/** * @author hushunfeng * * 大顶堆堆排序 * 从小到大排序 * */public class HeapSort { public static void main(String[] args) { int[] array = {10,20,30,40,50,60,70,80}; //先新建一个堆 createNewHeap(array); //去除最后一个元素，将根结点进行重新调整 int temp = 0; for(int j=7;j>=0;j--) { temp = array[0]; array[0] = array[j]; array[j] = temp; adjustNode(array,0,j); } for(int i=0;i<8;i++) { System.out.println(array[i]); } } /** * 将无序序列进行建堆 * @param array 要建的堆 */private static void createNewHeap(int[] array) { int heapNum = array.length; //根据建堆过程，先从第n/2个元素开始 //它是最后一个非终端结点 for(int i = heapNum/2-1; i >= 0; i--) { adjustNode(array,i,heapNum); } } /** * * 将parentNode为根结点的子树调整成一个最大堆 * @param array 要调整的无序序列，以数组的形式进行存储 * @param parentNode 以此结点为根结点建立子树 * */ //由于我们采用的是大顶堆,父结点要调整成大于子结点 private static void adjustNode(int[] array,int parentNode,int nodeNum) { //数组长度 // int arrayNum = array.length; //跳动的父结点游标(在子树层数大于2层时适用) int parentIndex = parentNode; //左子结点 int childLeftNode = 2*parentIndex+1; //右子结点 int childRightNode = 2*parentIndex+2; // int maxNode; //将可能要跳动的父结点的数据缓存起来 int temp = array[parentNode]; //不断地跳动父结点的游标 //防止右子结点不存在这种情况，不然会内存溢出 while(childLeftNode<nodeNum) { //此种情况下已经不存在右结点了 if(childLeftNode==nodeNum-1) { maxNode = childLeftNode; } else { //先比较左右子结点 if(array[childLeftNode]>array[childRightNode]) maxNode = childLeftNode; else maxNode = childRightNode; } //比较，交换位置 if(array[parentIndex]<array[maxNode]) { //将较大的子结点交换到父结点的位置 array[parentIndex] = array[maxNode]; array[maxNode] = temp; //往下移一层，再进行一次比较交换操作 //原先的子结点现在变成了父结点 parentIndex = maxNode; //下一层的子结点 childLeftNode = 2*parentIndex+1; childRightNode = 2*parentIndex+2; } //如果判断出父结点为最大，直接跳出循环 //无需再做交换动作，因为下面的元素都已经排成了大堆 else break; } } }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。