算法-排序-堆排序

文章将会同步到个人微信公众号:Android部落格

1.1 描述

堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了

1.2 代码

public class HelloWorld {
	static int[] numbers = {5,4,3,7,2,5,1,9,12,6,8,1,34};
	static int size = numbers.length;
	
	public static void buildMaxHeap(){
		int startPoint = size / 2 - 1;
		for(int index = startPoint;index >= 0;index--){
			 adjustMaxHeap(index);
		}
	}
	
	public static void adjustMaxHeap(int maxPoint){
		int leftPoint = 2 * maxPoint + 1;
		int rightPoint = 2 * maxPoint + 2;
		int maxNumber = numbers[maxPoint];
		int largestIndex = maxPoint;
		if(leftPoint < size && numbers[leftPoint] > maxNumber){
			largestIndex = leftPoint;
		}
		if(rightPoint < size && numbers[rightPoint] > maxNumber){
			largestIndex = rightPoint;
		}
		if(largestIndex != maxPoint){
			swap(maxPoint,largestIndex);
			adjustMaxHeap(largestIndex);
		}
	}
	
	public static void swap(int i,int j){
		int temp = numbers[i];
		numbers[i] = numbers[j];
		numbers[j] = temp;
	}
	
	public static void heapSort(){
		buildMaxHeap();
		for(int index = size - 1;index > 0;index--){
			swap(0,index);
			--size;
			adjustMaxHeap(0);
		}
	}
	
    public static void main(String []args) {
		heapSort();
		for(int value : numbers){
			System.out.println("quick value is:" + value);
		}
    }
}

1.3 总结

堆排序运用了二叉树的相关知识,使用大顶堆实现。Java中的PriorityQueue默认是小顶堆,可以通过改造Comparator成为小顶堆。

代码的基本流程是:

  • 先构建一颗二叉树,2n + 1为左节点,2n + 2为右节点,index从最后一个父节点开始创建,并不断循环到根节点。
  • 第一步创建的时候,父节点与值较大的子节点交换位置,以此循环。
  • 将二叉树根节点与最后一个叶子节点交换,同时将整棵树节点数减一,然后重新将整棵树重复第二步。
  • 在构建大顶堆的过程中,父节点与左右节点比较,选取值最大的节点作为父节点,并再去找这个最大值序号的左右节点,再去与自己的左右节点比较,重复进行,一直到最后一个父节点。

上述步骤的示意图如下: