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

参考文章：

堆排序就这么简单

堆排序分析：

 堆排序原理：

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

温馨提示：算法描述，排序原理搞不懂，先把最大（小）堆搞明白了，然后再看这篇文章。

堆排序算法描述：

• 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
• 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
• 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

堆排序原理图解：

Java 代码实现：

代码一：

package com.sorting.algorithm;public class HeapSort {		public static int[] heapSort(int[] array){		int n = array.length;		// 把数组堆化   heapify， 创建最大堆		for (int i = (n-1-1)/2; i >= 0; i--) {			siftDown(array,n,i);		}				// 将创建好的最大堆最大值放到数组最后，并重建除最大值以外的数组，建立最大堆，循环或递归进行		for (int i = n-1; i > 0; i--) {			swap(array,0,i);			siftDown(array,i,0);		}				return array;	}	private static void swap(int[] array, int i, int j) {		int temp = array[i];		array[i] = array[j];		array[j] = temp;	}	// 堆中原始的下沉操作	private static void siftDown2(int[] array, int n, int k) {		while(2*k+1 < n){			// j 代表左右子树最大值的下标			int j = 2*k +1;			if(j+1 < n && array[j] < array[j+1])				j++;						// 如果父节点 大于 左右子树节点就跳出循环			if(array[j] < array[k]) break;						// 将父节点和左右子树中的最大值交换位置			swap(array, k, j);						// 迭代看子树是否需要下沉操作			k=j;		}	}		// 堆中改进的下沉操作	private static void siftDown(int[] array, int n, int k) {		int e = array[k];		while(2*k+1 < n){			int j = 2*k +1;			if(j+1 < n && array[j] < array[j+1])				j++;			if(array[j] < array[k]) break;			array[k] = array[j];			k=j;		}		array[k] = e;	}	public static  void printArr(int[] array){		for (int i = 0; i < array.length; i++) {			if(i != array.length-1)				System.out.print(array[i] + ",");			else				System.out.println(array[i]);		}	}		public static void main(String[] args) {		int[] array = { 58,36,70,22,88,64,1,32 };		System.out.println("排序之前：");		printArr(array);		System.out.println("-------------------------------");				System.out.println("排序过程");		heapSort(array);				System.out.println("-------------------------------");		System.out.println("排序之后:");		printArr(array);			}}

代码二：

package com.sorting.algorithm;public class HeapSort2 {		// 用来记录变化的数组长度	private static int len;		public static int[] heapSort(int[] array){				len = array.length;				// 将数组堆化		buildMaxHeap(array);				// 将最大堆中的最大值放大数组的后面，数组长度减一，并重建最大堆 ，循环遍历，知道完成排序		while(len > 0){			printArr(array);			swap(array,0,len-1);			len--;			printArr(array);			adjustHeap(array,0);		}				return array;	}	// 调整最大堆，使它符合最大堆的性质	private static void adjustHeap(int[] array, int i) {		int maxIndex = i;		if(2*i 
   
    = 0; i--){			adjustHeap(array,i);		}	}		public static  void printArr(int[] array){		for (int i = 0; i < array.length; i++) {			if(i != array.length-1)				System.out.print(array[i] + ",");			else				System.out.println(array[i]);		}	}		public static void main(String[] args) {		int[] array = { 58,36,70,22,88,64,1,32 };		System.out.println("排序之前：");		printArr(array);		System.out.println("-------------------------------");				System.out.println("排序过程");		heapSort(array);				System.out.println("-------------------------------");		System.out.println("排序之后:");		printArr(array);			}	}
   

堆排序代码测试：

代码一：

代码二：

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