简单_堆排序算法
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
heap = new Heap(n, new Comparator() {
public int compare(Integer o1, Integer o2) {
o1; return o2 -
}
});
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("堆排序:");
/**
* 堆排序的思想是:
* 以最大堆为例
* ?把堆头和堆尾2个数交换
* ?将堆头到堆尾-1这个范围内的数进行堆化
* 重复上面2个步骤直到?步中要被堆化的数据长度为1
*
* 算法
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
* 堆[排序的时间，主要由建立初始]堆和反复重建堆这两
部分的时间开销构成，它们均是通过调用Heapify实现的。
堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能
较接近于最坏性能。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序，辅助空间为O(1)，
它是不稳定的排序方法。
*/
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 {
private Object[] heap;
private int size;
Comparator comp;
public Object[] getHeap() {
return heap;
}
public int count() {
return size;
}
public Heap(int n, Comparator 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) 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);
}
}
}
浙公网安备 33021202002483