堆排序

堆排序算法

首先介绍一下什么是堆，这里所说的堆其实是二叉堆。二叉堆是完全二叉树的应用，此外二叉堆又分为最小和最大二叉堆之分。最小二叉堆满足父节点的值小于儿子节点的值（除根节点外，因为根节点没有父节点）。很明显，说道这里最大二叉堆大家也就知道了，就不再叙述。

堆排序分为两个阶段：第一个阶段就是构建一个最小或者最大二叉堆。第二阶段就是采用选择排序的思想，将根节点交换到后面，再将其余的节点进行调整，成为新的二叉堆，重复进行，直到排序完成。下面将为大家展示如何用堆排序输出降序排列的序列。

按降序排列

package com.heapsort.yy;
/**
 * 堆排序算法
 *@author yuyang_csu
 *@data 2013-4-6
 */
public class HeapSort {
	//声明待排序的数组
	private int arr[];
	//重载构造函数
	public HeapSort(int arr[]){
		this.arr = arr;
	}
	//创建交换数组中两个元素的方法
	public void swap(int i,int j){
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
	/**
	 * 建立最小堆得方法
	 * @param arr:待排序数组
	 * @param lastindex：待排序数组的长度
	 */
	public void buildMinHeap(int [] arr,int lastindex){
		//从最后一个元素的父节点开始构建堆
		for(int root = lastindex-1/2;root>=0;root--){
			int left = root*2+1;
			//若当前节点存在子节点
			while(left<arr.length){
				//若当前节点存在右结点时，返回儿子节点中元素较小的节点
				if(left!=lastindex-1 && arr[left]>arr[left+1]){
					left++;
				}
				if(arr[root]>arr[left]){
					swap(root,left);
				}else{
					break;
				}
				left = left*2+1;
			}
		}
	}
	
	//构建堆排序的方法
	public void heapSort(){
		for(int i = arr.length;i>0;i--){
			buildMinHeap(arr,i);
			if(0==i-1){
				swap(0,i-1);
			}
		}
	}
	
	//显示数组的方法
	public void display(){
		for(int i = 0;i<arr.length;i++){
			System.out.print(arr[i]+"  ");
		}
	}
	
	public static void main(String[] args) {
		int [] arr = {31,41,59,26,53,58,97};
		HeapSort hs = new HeapSort(arr);
		hs.heapSort();
		hs.display();
	}
}

按升序排列

public class HeapSort {
	//待排序的数组
	private int arr[];

	//重载构造器
	public HeapSort(int[] arr) {
		this.arr = arr;
	}
	
	//交换数组两个元素的方法
	public void swap(int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
	
	//堆排序方法
	public void heapSort(int lastindex){
		//循环实现
//		while(lastindex>=0){
//			sort(lastindex);
//			swap(0,lastindex);
//			lastindex--;
//		}
		//递归实现
		if(lastindex>=0){
			sort(lastindex);
			swap(0,lastindex);
			//注意可以写成--lastindex或者lastindex-1,不能写成lastindex--
			heapSort(--lastindex);
		}
	}
	
	//创建最大堆得方法
	public void sort(int lastindex) {
		// 重最后一个节点的父节点开始遍历
		for (int i = (lastindex-1)/2; i >= 0; i--) {
			//声明左节点下标
			int left = 2 * i + 1;
			// 当节点有子节点的时候
			while (left <= lastindex) {
				// 当有右子节点的时候，返回儿子节点中元素较大的节点的下标
				if (left != lastindex && arr[left] < arr[left+1]){
					left++;
				}
				// 当父节点小于子节点中较大时，下滤
				if (arr[i] < arr[left]) {
					swap(i, left);
					left = left * 2 + 1;
				}else{
					break;
				}
			}
		}
	}
	
	//显示数组的方法
	public void display() {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + "  ");
		}
	}
	
	//主函数
	public static void main(String[] args) {
		int arr[] = { 1, 4, 7, 9, 2, 7, 3, 5 };
		HeapSort t = new HeapSort(arr);
		t.heapSort(arr.length-1);
		t.display();
	}
}

堆排序的时间复杂度：将一个序列调整为堆的时间复杂度为O（logN），因此堆排序的时间复杂度为O（NlogN）。

堆排序稳定性分析： 我们知道堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, ...1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法