简单_堆排序算法

package sunfa.sort;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;

public class HeapSort {
	public static void main(String[] args) {
		int n = 20;
		Random ran = new Random();
		int[] arr = new int[n];
		Heap<Integer> heap = new Heap<Integer>(n, new Comparator<Integer>() {
			public int compare(Integer o1, Integer o2) {
				return o2 - o1;
			}
		});
		for (int i = 0; i < n; i++) {
			int o = ran.nextInt(100);
			arr[i] = o;
			heap.add(o);
		}
		System.out.println(Arrays.toString(arr));
//		System.out.println(Arrays.toString(heap.getHeap()));
//		System.out.println(heap.getHeap()[heap.count()]);
//		heap.swap(heap.getHeap(), 1, heap.count());
//		System.out.println("swap:" + Arrays.toString(heap.getHeap()));
//		heap.heapify(1, heap.count());
		System.out.println(Arrays.toString(heap.getHeap()));

		System.out.println("堆排序：");
		/**
		 * 堆排序的思想是：<br>
		 * 以最大堆为例<br>
		 * ①把堆头和堆尾2个数交换<br>
		 * ②将堆头到堆尾-1这个范围内的数进行堆化<br>
		 * 重复上面2个步骤直到②步中要被堆化的数据长度为1<br>
		 * 
		 * 算法分析<br>
		 *　堆[排序的时间，主要由建立初始]堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。<br>
		　　堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。<br>
		　　由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。<br>
		　　堆排序是就地排序，辅助空间为O(1)，<br>
		　　它是不稳定的排序方法。<br>
		 */
		int last = heap.count();
		while (last - 1 > 1) {
			heap.swap(heap.getHeap(), 1, last--);
			if (last - 1 > 1) {
				heap.heapify(1, last);
			}
			System.out.println("堆化后:" + ",last:" + last
					+ Arrays.toString(heap.getHeap()));
		}
	}
}

class Heap<E> {
	private Object[] heap;
	private int size;
	Comparator<E> comp;

	public Object[] getHeap() {
		return heap;
	}

	public int count() {
		return size;
	}

	public Heap(int n, Comparator<E> c) {
		if (n < 0)
			throw new IllegalArgumentException("n:" + n);
		comp = c;
		heap = new Object[n];
	}

	public void add(E e) {
		if (size + 1 == heap.length)
			heap = Arrays.copyOf(heap, heap.length << 1);
		heap[++size] = e;
		fixUp(size);
	}

	private void fixUp(int k) {
		while (k > 1) {
			int p = k >>> 1;
			if (compare((E) heap[k], (E) heap[p]) > 0)
				break;
			swap((E[]) heap, k, p);
			k = p;
		}
	}

	public void swap(Object[] e, int a, int b) {
		Object t = e[a];
		e[a] = e[b];
		e[b] = t;
	}

	private int compare(E t1, E t2) {
		return comp == null ? (((Comparable<E>) t1).compareTo(t2)) : (comp
				.compare(t1, t2));
	}

	private void fixDown(int k) {
		int j;
		while ((j = k << 1) <= size) {
			if (j < size && compare((E) heap[j], (E) heap[j + 1]) > 0)
				j++;
			if (compare((E) heap[k], (E) heap[j + 1]) < 0)
				break;
			swap((E[]) heap, k, j);
			k = j;
		}
	}

	/**
	 * 对指定范围内的数据进行堆化
	 * @param a  开始索引
	 * @param b  结束索引
	 */
	public void heapify(int a, int b) {
		for (int i = b; i >= a; i--) {
			fixUp(i);
		}
	}
}