堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。通常所说的堆是一个近似完全二叉树的结构，并同时满足堆的性质：即最大堆子结点的关键字总是小于（如果是最小堆那就是大于）它的父节点。

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

通常堆是通过一维数组来实现的。在起始数组为 0 的情形中：

父节点 i 的左子节点在位置 (2*i+1);

父节点 i 的右子节点在位置 (2*i+2);

子节点 i 的父节点在位置 (i-1) / 2;

0 1 2

3 4 5 6 7 8 9 10

1、用大根堆排序的基本思想 （1）、 先将初始序列 R[0…n-1] 建成一个大根堆，此堆为初始的无序区 （2）、此时R[0]为序列中最大的数，将关键字最大的记录R[0]（即堆顶）和无序区的最后一个记录R[n-1]交换，由此得到新的无序区R[0…n-2]和有序区R[n-1] （3）、由于交换后新的根 R[1] 可能违反堆性质，故应将当前无序区R[0…n-2]调整为堆。然后再次将R[0…n-2]中关键字最大的记录R[0]和该区间的最后一个记录R[n-2]交换，由此得到新的无序区R[0…n-3]和有序区R[n-2…n-1]，同样要将R[0…n-3]调整为堆。……直到无序区只有一个元素为止。

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

2、大根堆排序算法的基本操作：

（1）、 初始化操作：将R[0…n-1]构造为初始堆；

（2）、 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。

注意：

（1）、只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。

（2）、用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止

最差时间复杂度： O(n logn)

最优时间复杂度： O(n logn)

平均时间复杂度： O(n logn)

最差空间复杂度： O(1)

稳定性：不稳定

步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

再简单总结下堆排序的基本思路：

a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序

代码实现

package sortdemo; import java.util.Arrays; /** * Created by chengxiao on 2016/12/17. * 堆排序demo */ public class HeapSort { public static void main(String []args){ int []arr = {9,8,7,6,5,4,3,2,1}; sort(arr); System.out.println(Arrays.toString(arr)); } public static void sort(int []arr){ //1.构建大顶堆 for(int i=arr.length/2-1;i>=0;i--){ //从第一个非叶子结点从下至上，从右至左调整结构 adjustHeap(arr,i,arr.length); } //2.调整堆结构+交换堆顶元素与末尾元素 for(int j=arr.length-1;j>0;j--){ swap(arr,0,j);//将堆顶元素与末尾元素进行交换 adjustHeap(arr,0,j);//重新对堆进行调整 } } /** * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上） * @param arr * @param i * @param length */ public static void adjustHeap(int []arr,int i,int length){ int temp = arr[i];//先取出当前元素i for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始 if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点 k++; } if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换） arr[i] = arr[k]; i = k; }else{ break; } } arr[i] = temp;//将temp值放到最终的位置 } /** * 交换元素 * @param arr * @param a * @param b */ public static void swap(int []arr,int a ,int b){ int temp=arr[a]; arr[a] = arr[b]; arr[b] = temp; } }

图解

堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)…1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。