简单_堆排序算法

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);}}}