제6장 무더기 정렬
11245 단어 더미 정렬
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));
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
석 주 - 데이터 구조 - 선택 & 쌓 기 정렬예전 에 내 가 가장 좋아 했 던 것 은 순 서 를 선택 하 는 것 이 었 다. 현재 요소 의 뒤에서 가장 작은 요 소 를 선택 하여 교환 하 는 것 이다. 쌓 기 정렬 은 빠 른 정렬 의 개선 으로 거품 처럼 빠르...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
