java干货来袭!新手必看系列之Java堆排序法!_java自学_java相关资讯_成都java培训机构

java干货来袭!新手必看系列之Java堆排序法!

  • 作者:创始人
  • 发表时间:2021-11-17 09:35:56

对于刚学习Java的小白,或者刚要学习Java的小白来说,可能并不很清楚Java八大排序法中堆排序,那么什么是堆排序?其代码又是怎么样的呢?新手必看!

什么是堆排序?

堆排序 堆排序(Heap Sort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

Java堆排序法!

堆排序的思路;如果要把堆排序的序列看成一棵树的顺序储存的二叉树,调整他们之间的一个储蓄序,让它们之间成为一个“堆”。然后将根节点和“堆”的最后一个节点进行交换,让前面(n-1)个数重新调整成为“堆”。以此类推,一直到只有两个节点的“堆”,并在它们之间进行交换,最后得到的便有n个节点的一个有序序列。从对算法的描述来看,堆排序主要是需要以下两个过程,一个是建立“堆”,第二个是反复强调元素之间位置的交换。所以堆排序的过程由两个函数组成,第一个是建“堆”的渗透函数,第二个是反复强调用渗透参数实习排序的函数。


Java实习代码:

public class HeapSort {

    /**

     * 构建大顶堆

     */

    public static void adjustHeap(int[] a, int i, int len) {

        int temp, j;

        temp = a[i];

        for (j = 2 * i; j < len; j *= 2) {// 沿关键字较大的孩子结点向下筛选

            if (j < len && a[j] < a[j + 1])

                ++j; // j为关键字中较大记录的下标

            if (temp >= a[j])

                break;

            a[i] = a[j];

            i = j;

        }

        a[i] = temp;

    }


    public static void heapSort(int[] a) {

        int i;

        for (i = a.length / 2 - 1; i >= 0; i--) {// 构建一个大顶堆

            adjustHeap(a, i, a.length - 1);

        }

        for (i = a.length - 1; i >= 0; i--) {// 将堆顶记录和当前未经排序子序列的最后一个记录交换

            int temp = a[0];

            a[0] = a[i];

            a[i] = temp;

            adjustHeap(a, 0, i - 1);// 将a中前i-1个记录重新调整为大顶堆

        }

    }


    public static void main(String[] args) {

        int a[] = { 51, 46, 20, 18, 65, 97, 82, 30, 77, 50 };

        heapSort(a);

        System.out.println(Arrays.toString(a));

    }

关注成都知了堂Java培训,带你了解更多Java相关问题,以及了解Java更多干货知识。