×
文章路径: Java > 算法 > 排序

堆排序HeapSort

发表于3年前(Dec 24, 2014 10:11:34 AM)  阅读 488  评论 0

分类: Java 算法 排序

标签: buildmaxheap heapsort maxheapify 堆排序 最大堆

堆积排序(Heapsort)是指利用堆积树(堆)这种资料结构所设计的一种排序算法,可以利用数组的特点快速定位指定索引的元素。

堆排序原理有点点复杂,文字我描述不清楚,画图是最有助于理解了的,想深入研究的朋友建议参考算法导论中有关堆排序的描述。

堆排序中有几个重要的过程:Max-Heapify,是用来保持最大堆性质;Build-Max-Heap是用来把一个无序数组建立成最大堆;Heap-Sort则是把一个数组利用最大堆性质进行原地排序。

package sort;

/**
 * 堆排序
 * @author lihui
 *
 */
public class HeapSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
//		int[] a = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
		int[] a = {4, 1, 2, 2, 16, 9, 9, 9, 8, 7};
		//4	1	10	14	16	9	3	2	8	7	
//		int[] a = {1, 14, 10, 8, 7, 9, 3, 2, 4};
//		buildMaxHeap(a);
//		maxHeapify(a, 0);
		heapSort(a);
		for(int i=0;i<a.length;i++) {
			System.out.print(a[i]+"\t");
		}
	}
	
	/**
	 * 堆排序
	 * @param a
	 */
	public static void heapSort(int[] a) {
		//先将数组构造成一个最大堆
		buildMaxHeap(a);
		for(int i=a.length-1;i>0;i--) {
			//堆顶的元素为堆中最大元素
			//将堆顶的元素依次倒序交换放入数组
			int temp = a[i];
			a[i] = a[0];
			a[0] = temp;
			//将剩下的堆元素再调整成最大堆
			maxHeapify(a, 0, i);
		}
	}
	
	/**
	 * 迭代调用maxHeapify建立最大堆
	 * 数组长度为n,叶子结点的索引从int(n/2)
	 * @param a
	 */
	public static void buildMaxHeap(int[] a) {
		//m为最后一个有子树的结点
		int m = a.length/2-1;
		for(int i=m;i>=0;i--) {
			maxHeapify(a, i, a.length);
		}
	}
	
	
	/**
	 * 将第i个结点的子树调整成最大堆
	 * i从0取的话,他的左儿子下标为2*i+1,右儿子下标为2*i+2
	 * @param a 堆数组
	 * @param i 要调整的结点
	 * @param heapSize 存放在数组中堆的元素个数
	 */
	public static void maxHeapify(int[] a, int i, int heapSize) {
		int temp = a[i];
		boolean flag = false;
		//如果两个儿子都存在
		if(2*i+2<=heapSize-1) {
			//跟左儿子交换的情形:左儿子比右儿子大,且左儿子比父大
			//注:这里一定必须是左儿子大于或等于右儿子,而不是大于
			if(a[2*i+1]>=a[2*i+2]&&a[2*i+1]>a[i]) {
				a[i] = a[2*i+1];
				a[2*i+1] = temp;
				flag = true;
			} else if(a[2*i+2]>=a[2*i+1]&&a[2*i+2]>a[i]) {
				a[i] = a[2*i+2];
				a[2*i+2] = temp;
				flag = true;
			}
			//如果发生过交换,且他们的儿子还有子,继续迭代
			if(flag) {
				if(2*(2*i+1)+1<=heapSize-1) {
					maxHeapify(a, 2*i+1, heapSize);
				}
				if(2*(2*i+2)+1<=heapSize-1) {
					maxHeapify(a, 2*i+2, heapSize);
				}
			}
		//只有一个儿子
		} else if(2*i+1==heapSize-1){
			if(a[i]<a[2*i+1]) {
				a[i] = a[2*i+1];
				a[2*i+1] = temp;
			}
		}
	}

}
堆排序的时间复杂度为O(nlog n) ,同合并排序,但相比合并排序他的优点是可以在原数组上实现排序。

发表评论