堆排序是基于完全二叉树的排序。把一个完全二叉树调整为堆，以及每次堆顶元素交换后进行调整的时间复杂度均为O(lgn),所以堆排序的时间复杂度为O(nlgn)。堆排序的空间复杂度为O(1).堆排序是一种不稳定的排序。

堆排序的步骤为:

  1.将待排序的数组构建为一个最大堆

java代码实现:

import java.util.Arrays;/** * 堆排序 * 1.将待排序的数组构建为一个最大堆 * 2.在最大堆的基础上排序 * 	(1)把堆顶a[0]元素(最大的元素)和当前最大堆的最后一个元素交换 *  (2)最大堆元素减一 *  (3)调整跟节点使它满足最大堆  */public class HeapSort {	/**	 *@Description	 * @param args	 */	public static void main(String[] args) {		// TODO Auto-generated method stub		int arr[] = {10,50,32,5,76,9,40,88};		heapSort(arr);		System.out.println(Arrays.toString(arr));	}		public static void heapSort(int arr[]){		initMaxHeap(arr);		int n = arr.length,temp;		for(int i=n-1;i>=0;i--){			//把堆顶a[0]元素(最大的元素)和当前最大堆的最后一个元素交换			temp = arr[0];			arr[0] = arr[i];			arr[i] = temp;			//逐渐缩小堆的大小			createMaxHeap(arr,0,i);		}	}		//初始化最大堆	public static void initMaxHeap(int arr[]){		int n = arr.length;		//从第一个非叶节点开始构造最大堆，注意完全二叉树的性质		for (int i = (n-1)/2; i >= 0; i--) {			createMaxHeap(arr,i,n);		}	}		/**	 *@Description 创建最大堆	 * @param arr 需要创建堆的数组	 * @param i 开始下标	 * @param n 堆的大小	 */	public static void createMaxHeap(int arr[],int i,int n){		int left = 2*i+1;		int	right = 2*i+2;		int largest = i;		if(left
    
     arr[largest]){			largest = left; 		}		if(right
     
      arr[largest]){			largest = right;		}		if(largest!=i){			int temp = arr[i];			arr[i] = arr[largest];			arr[largest] = temp;			//递归地构建孩子节点，使其满足最大堆的特性			createMaxHeap(arr,largest,n);		}	} 	}