ヒープソートアルゴリズム(わかりやすい)(大頂ヒープ)
3866 ワード
package com.czf.sortTest.sort;
/**
*
*
* @author czf
* @date 20180726
*/
public class HeapSort {
public static void heapSort(int[] data) {
HeapNode[] heap = initHeap(data);
sort(heap, heap.length - 1, data);
}
/**
*
* N/2
*
* @param data
* @return
*/
private static HeapNode[] initHeap(int[] data) {
HeapNode[] heap = new HeapNode[data.length];
for (int i = 0; i < data.length; i++) {
heap[i] = new HeapNode(data[i]);
}
for (int i = 0; i < data.length; i++) {
int left = 2 * i + 1, right = 2 * i + 2;
heap[i].left = left < data.length ? heap[left] : null;
heap[i].right = right < data.length ? heap[right] : null;
}
for (int i = heap.length / 2; i >= 0; i--) {
adjustDown(heap[i]);
}
return heap;
}
/**
*
*
* @param heap
* @param end end ,
*/
private static void sort(HeapNode[] heap, int end, int[] data) {
data[end] = heap[0].value;
if (end <= 0)
return;
swap(heap[0], heap[end]);//
deleteLastNode(heap, end);
adjustDown(heap[0]);//
sort(heap, --end, data);
}
/**
*
*
* @param node
*/
private static void adjustDown(HeapNode node) {
while (node.left != null || node.right != null) {
if (node.left == null) {
if (node.right.value > node.value) {
swap(node.right, node);
node = node.right;
continue;
}
}
if (node.right == null) {
if (node.left.value > node.value) {
swap(node.left, node);
node = node.left;
continue;
}
}
if (node.left != null && node.right != null) {//
if (node.left.value >= node.right.value && node.left.value > node.value) {
swap(node.left, node);
node = node.left;
continue;
}
if (node.right.value > node.left.value && node.right.value > node.value) {
swap(node.right, node);
node = node.right;
continue;
}
}
}
}
private static void deleteLastNode(HeapNode[] heap, int end) {
int fatherIndex1 = end / 2;
if (heap[fatherIndex1].left == heap[end])
heap[fatherIndex1].left = null;//
int fatherIndex2 = end / 2 - 1;
if (fatherIndex2 >= 0 && heap[fatherIndex2].right == heap[end])
heap[fatherIndex2].right = null;//
}
private static void swap(HeapNode i, HeapNode j) {
int temp = i.value;
i.value = j.value;
j.value = temp;
}
}
class HeapNode {
HeapNode left;
HeapNode right;
int value;
public HeapNode(int value) {
this.value = value;
}
}
package com.czf.sortTest;
import com.czf.sortTest.sort.HeapSort;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
// write your code here
int[] data = {45, 44, 23, 22, 1, 43, 99, 56, 0, 100, 45, 45, 45, 5, 45, 6, 45, 25623453, 258};
//int[] data = {45, 44, 23, 22, 1, 43, 99, 56};
// : :
// QuickSort.quickSort(data, 0, data.length - 1);
// :
HeapSort.heapSort(data);
System.out.println("sorted: " + Arrays.toString(data));
}
}