本文共 1693 字，大约阅读时间需要 5 分钟。

堆排序算法步骤：

1、把无序数组构建成二叉堆。需要从小到大排序，则构建成最大堆；需要从大到小排序，则构建成最小堆。 2、循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶

复杂度

空间复杂度：因为没有开辟额外的集合空间，所以复杂度为O(1)

时间复杂度 O(nlogn): 二叉堆的节点“下沉”是堆排序算法的基础，这个复杂度是O(logn) 第1步，把无序数组构建成二叉堆，这一步的时间复杂度是O(n) 第2步，需要进行n-1次循环，每次循环调用一次下沉方法，所以第2步的计算规模是(n-1)*logn,所以整体的时间复杂度是O(nlogn)

和快排的区别

    相同点：平均时间复杂度都是O(nlogn),都是步稳定排序     不同点：         1、快排的最坏时间复杂度是O(n2平方),堆排序的最坏时间复杂度是O(nlogn)         2、快排的评价空间复杂度O(logn),堆排序的空间复杂度是O(1)

public class HeapSoft {    public static void downAdjust(int[] arr,int parentIndex,int length){        int childIndex = parentIndex * 2 + 1;        //保存父节点的值，用于最后赋值        int temp = arr[parentIndex];        while (childIndex < length){            //如果又右孩子，且右孩子大于左孩子的值，则定位到右孩子            if(childIndex + 1 < length && arr[childIndex + 1] > arr[childIndex]){                childIndex ++ ;            }            //如果父节点大于任何一个孩子的值，则直接推出            if(temp >= arr[childIndex]){                break;            }            //无须真正交互，单向赋值即可            arr[parentIndex] = arr[childIndex];            parentIndex = childIndex;            childIndex = 2 * childIndex + 1 ;        }        arr[parentIndex] = temp;    }    public static void heapSort(int[] arr){        //把无序数组构建成最大堆        for(int i=(arr.length - 2)/2;i>=0;i--){            downAdjust(arr,i,arr.length);        }        System.out.println(Arrays.toString(arr));        for (int i=arr.length - 1;i>0;i--){            //最后一个元素和第一个元素进行交换            int temp = arr[i];            arr[i] = arr[0];            arr[0] = temp;            downAdjust(arr,0,i);        }    }    public static void main(String[] args) {        int[] arr = new int[]{1,3,2,6,5,7,8,9,10,0};        heapSort(arr);        System.out.println(Arrays.toString(arr));    }}

 

转载地址：http://dqsvi.baihongyu.com/