输入一个数m表示要排序的数的多少,随机生成m个0~10000之间的数进行堆排序。
import java.util.Random;
import java.util.Scanner;
import org.junit.Test;
public class Heap_Sort {
public static void makeHeap(int A[], int n) {
A[n] = A[0];
for (int i = n / 2; i >= 1; i--) {
shift_down(A, n, i);
}
}
private static void shift_down(int A[], int n, int i) {
boolean done = true;
while (done && i * 2 <= n) {
i = i * 2;
if ((i + 1) <= n && A[i + 1] > A[i])
i++;
if (A[i / 2] < A[i])
swap(A, i / 2, i);
}
}
private static void swap(int a[], int x, int y) {
int t;
t = a[x];
a[x] = a[y];
a[y] = t;
}
public static void sortHeap(int A[], int n) {
makeHeap(A, n);
swap(A, n, 1);
for (int i = n - 1; i > 1; i--) {
shift_down(A, i, 1);
swap(A, i, 1);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int A[] = new int[n + 1];
Random r = new Random();
for (int i = 0; i < n; i++) {
A[i] = r.nextInt(10000);
}
sortHeap(A, n);
for (int i = 1; i <= n; i++) {
System.out.print(A[i] + "\t");
}
}
}