大根堆排序

xiaoxiao2021-02-28  6

1、基本思想

堆是一种特殊的树形数据结构,其每个节点都有一个值,通常提到的堆都是指一颗完全二叉树,根结点的值小于(或大于)两个子节点的值,同时,根节点的两个子树也分别是一个堆。  堆排序就是利用堆(假设利用大顶堆)进行排序的方法。它的基本思想是,将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根节点。将它移走(其实就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的 n-1 个序列重新构造成一个堆,这样就会得到 n 个元素中次大的值。如此反复执行,便能得到一个有序序列了。 堆排序的实现需要解决的两个关键问题: (1)将一个无序序列构成一个堆。 

(2)输出堆顶元素后,调整剩余元素成为一个新堆。

堆排序的时间复杂度为O(nlogn),由于堆排序对原始记录的状态并不敏感,因此它无论是最好、最坏和平均时间复杂度均为O(nlogn)。空间复杂度为O(1),为不稳定排序。

public class HeapSort{    public static void main(String[] args)    {        int[] arr = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};        heapSort(arr);        printHeap(arr);    }    //堆排序函数    public static void heapSort(int[] arr)    {        int len = arr.length;        buildHeap(arr, len); //首次建堆,建成一个完整的大顶堆(根节点为最大值)        for (int i = 0; i < len; i++)        {            swap(arr, 0, len - 1 - i); //将堆顶元素(通过调整堆获得的最大值)和最后一个交换(剩余未排好序部分的最后一个)            adjustHeap(arr, len - 1 - i, 0); //之后每次从堆顶开始调整,最大的值将上升到根节点        }    }    //第一次建堆的过程    public static void buildHeap(int[] arr, int maxlen)    {        int len = maxlen / 2 - 1; //完全二叉树的最后一个非叶子结点        for (int i = len; i >= 0; i--)        {            adjustHeap(arr, maxlen, i);        }    }    /**    * maxlen 此次调整堆的最大元素个数(因为堆排序过程中,后面已经调整好的就不需要调整了)    * i 表示此次调整堆的父节点    * */    public static void adjustHeap(int[] arr, int maxlen, int i)    {        int left = 2 * i + 1; //获得该父节点的左孩子        int right = 2 * i + 2; //获得该父节点的右孩子         int maxpos = i;        while (left < maxlen)        {            if (right < maxlen && arr[maxpos] < arr[right])            {                maxpos = right;            }            if (arr[maxpos] < arr[left])            {                maxpos = left;            }            if (maxpos != i)            {                swap(arr, i, maxpos);                i = maxpos; //继续向下调整,因为此次调整可能会破坏原来下面的堆                left = 2 * i + 1;                right = 2 * i + 2;            }            else            {                break;            }        }    }    //交换堆中任意两个数    public static void swap(int[] arr, int from, int to)    {        int temp = arr[from];        arr[from] = arr[to];        arr[to] = temp;    }    //打印堆中的数据    public static void printHeap(int[] arr)    {        int len = arr.length;        for (int i = 0; i < len; i++)        {            System.out.print(arr[i] + " ");        }        System.out.println();    }}

转载请注明原文地址: https://www.6miu.com/read-1950178.html

最新回复(0)