堆排序-Java实现

女爷i 2022-02-23 12:40 213阅读 0赞

## 堆排序思想 ##

对于给定的n个数据，初始时将n维数组看成一颗二叉树，若需要**从小到大**排序，将其调整为**小顶堆**（若**从大到小**排序，调整为**大顶堆**），输出堆顶元素，然后将堆的最后一个元素与堆顶元素（二叉树的根节点）互换，再接着将前n-1个元素（不包括最小数）重新调整为一个最小堆，再次交换堆顶与当前堆的最后一个元素，直到当前堆中只剩最后一个元素为止。程序的输出即为从小到大排序的数列。

## Java实现 ##

public class Main {
        public static void main(String[] args) {
            int[] a = {5,4,9,8,7,6,0,1,3,2};
            int len = a.length;
            MinHeapSort(a, len);
        }
    
        public static void adjustMinHeap(int[] a, int pos, int len){
            int child, temp;
            for(temp = a[pos]; (2*pos+1)<=len; pos = child){
                child = 2*pos + 1;
                if(child<len && a[child]>a[child+1])  // 有右子节点
                    child++;
                if(a[child]<temp)
                    a[pos] = a[child];
                else
                    break;
            }
            a[pos] = temp;
        }
    
        public static void MinHeapSort(int[] a, int len){
            int i;
            for(i=(len-1)/2;i>=0;i--)   // 调整至小顶堆，从最后一个有孩子的结点开始往上调整
                adjustMinHeap(a, i, len-1);
            for(i=len-1;i>=0;i--){
                System.out.println(a[0]);
                swap(a, 0, i);
                adjustMinHeap(a, 0, i-1); // 调整小顶堆
            }
        }
    
        public static void swap(int[] a, int i, int j){
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }

## 输出 ##

0
    1
    2
    3
    4
    5
    6
    7
    8
    9

发表评论取消回复

表情：

评论列表（有 0 条评论，213人围观）

还没有评论，来说两句吧...

相关阅读

相关 java实现堆排序

一、堆排序基本介绍 1. 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为 O(nlogn)，它也是不稳定...

曾经终败给现在/ 2024年04月19日 08:47/ 0 赞/ 62 阅读

相关 Java实现堆排序

> 堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二

电玩女神/ 2023年08月17日 15:43/ 0 赞/ 102 阅读

相关 java实现堆排序

package cn.sort.heap; import cn.sort.utils.ArrayUtils; / Cre

小咪咪/ 2022年08月01日 15:46/ 0 赞/ 192 阅读

相关选择排序----堆排序----java实现

（1）小顶堆假设有n个元素的序列，k0-kn,如果将这组数据排成一棵完全二叉树，则此树的特点是：树中所有节点的值都小于其左右节点的值，此树的根必然是最小的；（2

雨点打透心脏的1/2处/ 2022年07月21日 00:26/ 0 赞/ 198 阅读

相关 Java实现堆排序算法

这里列出自己写的两个堆排序算法，第一个是之前写的，当时不知道堆调整的思想，第二个是优化堆调整后的方法。这是第一个：之前只知道如何建堆，不知道算法导论上还有如此巧

淡淡的烟草味﹌/ 2022年07月21日 00:16/ 0 赞/ 169 阅读

相关堆排序（java实现）

一、前言堆是一个数组，它可以看成近似的完全二叉树。表示堆的数组包括两个属性：A.length数组元素的个数，A.heapSize表示多少个元素存在数组中。这里的关系是：

深碍√TFBOYSˉ_/ 2022年05月31日 06:49/ 0 赞/ 178 阅读

相关 1.堆排序java实现

public class HeapSort { / 调整aaray[parent,end]范围为最大堆 @param a

落日映苍穹つ/ 2022年03月12日 20:15/ 0 赞/ 175 阅读

相关 Java实现堆排序

[Java实现堆排序 Heap Sort][Java_ _ Heap Sort] 堆排序与[快速排序][Link 1]，[归并排序][Link 2]一样都是时间复杂度

小咪咪/ 2022年02月26日 06:24/ 0 赞/ 195 阅读

相关堆排序-Java实现

堆排序思想对于给定的n个数据，初始时将n维数组看成一颗二叉树，若需要从小到大排序，将其调整为小顶堆（若从大到小排序，调整为大顶堆），输出堆顶元素，然后将堆的最后一个元素

女爷i/ 2022年02月23日 12:40/ 0 赞/ 214 阅读

相关堆排序 java 实现

public class HeepSort { private static void heepSort(int[] arr) { in

系统管理员/ 2021年09月28日 13:20/ 0 赞/ 292 阅读