堆排序程序

Java实现的堆排序

import java.util.Comparator;
import java.util.Collections;
import java.util.ArrayList;
import java.util.List;

public class HeapSort {

public static class DefaultComparator implements Comparator {
public DefaultComparator() {}

public int compare(Object a, Object b) {
return ((Comparable)a).compareTo(b);
}
}


public static void sort(Object[] A) {
sort(A, new DefaultComparator());
}


public static void sort(Object[] A, Comparator c) {
ArrayList list = new ArrayList(A.length);

for (int i=0; i

public static void sort(List A) {
sort(A, new DefaultComparator());
}

public static void sort(List A, Comparator c) {
int heapsize = A.size();

buildHeap(A, c);

for (int i = heapsize; i>0; i--) {
Collections.swap(A, 0, i-1);

heapsize--;
siftdown(A, 0, heapsize, c);
}
}

private static void buildHeap(List A, Comparator c){
int heapsize = A.size();

for (int i=heapsize/2; i>=0; i--){
siftdown(A, i, heapsize, c);
}
}

private static void siftdown(List A, int i, int heapsize, Comparator c){
int largest = i; // becomes the largest of A[i], A[2i], & A[2i+1]

do {
i = largest;
int left = (i << 1) + 1;   // left=2*i+1
int right = left + 1;

if (left < heapsize){
largest = indexOfLargest(A, largest, left, c);

if (right < heapsize) {
largest = indexOfLargest(A, largest, right, c);
}
}

if (largest != i) {
Collections.swap(A, i, largest);
}
} while (largest != i);
}

private static int indexOfLargest(List A, int i, int j, Comparator c){
if ( c.compare(A.get(i), A.get(j)) < 0) {
return j;
} else {
return i;
}
}

}