欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

堆排序java实现 博客分类: java数据结构&算法  

程序员文章站 2024-02-24 19:58:58
...
/**
 * 大根堆,从小到大排序
 * 
 * @author Administrator
 * 
 */
public class HeapSorter {
	private static int N = 10000000;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] arr = new int[N + 1];
		for (int i = 0; i <= N; i++) {
			arr[i] = ((Double) (Math.random() * 1000)).intValue();
		}
		initHeap(arr, N);
		System.out.println("init check's result is " + checkInit(arr));
		doSort(arr);
		System.out.println("result check's result is " + checkResult(arr));
	}

	private static boolean checkInit(int[] arr) {
		boolean result = true;
		for (int i = 1; i <= N; i++) {
			result = result && isHeap(arr, i, N);
		}
		return result;
	}

	private static boolean checkResult(int[] arr) {
		boolean result = true;
		for (int i = 1; i <= N - 1; i++) {
			result = result && (arr[i] <= arr[i + 1]);
		}
		return result;
	}

	private static void doSort(int[] arr) {
		int maxIndex = N;
		while (maxIndex > 0) {
			arr[0] = arr[maxIndex];
			arr[maxIndex] = arr[1];
			arr[1] = arr[0];
			maxIndex--;
			buildHeap(arr, 1, maxIndex);
		}
	}

	private static void initHeap(int[] arr, int maxIndex) {
		for (int p = maxIndex / 2; p >= 1; p--) {
			buildHeap(arr, p, maxIndex);
		}
	}

	private static boolean isHeap(int[] arr, int i, int maxIndex) {
		boolean result = false;
		if (i > maxIndex / 2) {
			result = true;
		} else {
			if (arr[i] >= arr[2 * i]
					&& ((2 * i + 1 > maxIndex) || arr[i] >= arr[2 * i + 1])) {
				result = true;
			}
		}
		return result;
	}

	private static void buildHeap(int[] arr, int p, int maxIndex) {
		if (!isHeap(arr, p, maxIndex)) {
			int larger = p * 2;
			if (p * 2 + 1 <= maxIndex && arr[p * 2] < arr[p * 2 + 1]) {
				larger = p * 2 + 1;
			}
			arr[0] = arr[larger];
			arr[larger] = arr[p];
			arr[p] = arr[0];
			buildHeap(arr, larger, maxIndex);
		}
	}

}

 

堆排序的实现过程主要分2步,

第一步:初始化堆。

第二步:将堆的根(最大值)与最后一个元素交换,后针对剩余的无序的数列继续构造堆,以产生新的最大值

构造堆的过程:1.判断根是否满足堆的定义,如果不满足则交换,交换后判断发生交换后的新根是否满足根得定义,直到交换后的新根满足堆定义,则该子树堆构造完成。叶子节点都满足堆的定义

 

可以优化的地方:最后一个元素为堆里较小的值,将根与其交换后构造根得话比较与交换的次数较多。

 

 

 

 

 

“堆”定义

  n个关键字序列Kl,K2,…,Kn称为(Heap),当且仅当该序列满足如下性质(简称为堆性质):

  (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n) //ki相当于二叉树的非叶结点,K2i则是左孩子,k2i+1是右孩子

     若将此序列所存储的向量R[1..n]看做是一棵完全二叉树 的存储结构,则堆实质上是满足如下性质的完全二叉树:   树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

 【例】关键字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足堆性质(1)和(2),故它们均是堆,其对应的完全二叉树分别如小根堆示例和大根堆示例所示。