第六章スタックの順序付け
11163 ワード
これからはできるだけ反復で再帰を使わないようにしましょう.再帰は自分を楽にしただけですが、パソコンの負担が増えました.
package chap06_Heap_Sort;
import static org.junit.Assert.*;
import java.util.Arrays;
import org.junit.Test;
public class SortAlorithms {
/**
*
*
* @param i
* @return
*/
protected static int parent(int i) {
if (i == 0)
return i;
return (i - 1) / 2;
}
/**
* i
*
* @param i
* @return
*/
protected static int left(int i) {
return 2 * i + 1;
}
/**
* i
*
* @param i
* @return
*/
protected static int right(int i) {
return 2 * (i + 1);
}
/**
* ( )
*
* @param a
* @param i
*/
protected static void maxHeapify1(int[] a, int i, int SIZE) {
int l = left(i);
int r = right(i);
int tmp;
if (l < SIZE & r < SIZE) {
if (a[i] >= a[l] & a[i] >= a[r])
return;
else if (a[l] > a[r]) {
tmp = a[i];
a[i] = a[l];
a[l] = tmp;
i = l;
} else {
tmp = a[i];
a[i] = a[r];
a[r] = tmp;
i = r;
}
} else if (l < SIZE) {
if (a[i] < a[l]) {
tmp = a[i];
a[i] = a[l];
a[l] = tmp;
i = l;
}
} else {
return;
}
maxHeapify1(a, i, SIZE);
}
/**
* ， i size（ size ）
*
* @param a
* @param i
* @param SIZE
*/
protected static void maxHeapify(int[] a, int i, int SIZE) {
int l = left(i);
int r = right(i);
int tmp;
while (l < SIZE & r < SIZE) {
if (a[i] >= a[l] & a[i] >= a[r])
return;
else if (a[l] > a[r]) {
tmp = a[i];
a[i] = a[l];
a[l] = tmp;
i = l;
} else {
tmp = a[i];
a[i] = a[r];
a[r] = tmp;
i = r;
}
l = left(i);
r = right(i);
}
if (l < SIZE) {
if (a[i] < a[l]) {
tmp = a[i];
a[i] = a[l];
a[l] = tmp;
i = l;
}
}
return;
}
/**
* a , ，
*
* @param a
*/
protected static void buildMaxHeap(int[] a) {
int n = a.length;
for (int i = n / 2; i >= 0; i--) {
maxHeapify1(a, i, n);
}
}
/**
*
*
* @param n
*/
static void heapSort(int[] n) {
buildMaxHeap(n);
int l = n.length;
int size = l;
int tmp;
for (int i = l - 1; i > 0; i--) {
tmp = n[0];
n[0] = n[i];
n[i] = tmp;
size--;
maxHeapify(n, 0, size);
}
}
@Test
public void testName() throws Exception {
// int[] a = { 2, 5, 3, 7, 8, 12, 0, 2, 45, 32 };
int[] a = { 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 };
// buildMaxHeap(a);
// heapSort(a);
maxHeapify1(a, 0, 10);
System.out.println(Arrays.toString(a));
}
}