Skip to content

Instantly share code, notes, and snippets.

@sys1yagi
Created August 23, 2012 09:45
Show Gist options
  • Save sys1yagi/3434812 to your computer and use it in GitHub Desktop.
Save sys1yagi/3434812 to your computer and use it in GitHub Desktop.
javaでヒープソート 効率はよくない
package jp.dip.sys1.yagi.sort;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
public class HeapSort {
/**
* ヒープソートやで
* @param list ソート対象のリスト
* @param comp 要素の比較関数
*/
public static <T> void sort(List<T> list, Comparator<T> comp){
for (int i = 0; i < list.size(); i++) {
HeapSort.build(list, 0, i, comp);
}
}
/**
* 指定したoffset以降の要素をヒープ構造に並べ替える
* @param list 対象のリスト
* @param index ノードのインデックス
* @param offset 未ソート状態のリストの開始位置
* @param comp 比較関数
*/
public static <T> void build(List<T> list, int index, int offset, Comparator<T> comp) {
T l = HeapSort.left(list, index, offset);
if (l != null) {
HeapSort.build(list, 2 * index + 1, offset, comp);
l = HeapSort.left(list, index, offset);
HeapSort.swap(list, index, offset, l, 2 * index + 1, comp);
}
T r = HeapSort.right(list, index, offset);
if (r != null) {
HeapSort.build(list, 2 * index + 2, offset, comp);
r = HeapSort.right(list, index, offset);
HeapSort.swap(list, index, offset, r, 2 * index + 2, comp);
}
}
/**
* 子ノードを取り出す
* @param list 対象のリスト
* @param index ノードのインデックス
* @param offset 未ソート状態のリストの開始位置
* @param leaf 左か右か。1=左 2=右
* @return 子ノード。存在しない場合はnull
*/
public static <T> T child(List<T> list, int index, int offset, int leaf) {
int i = 2 * index + leaf + offset;
if (list.size() <= i) {
return null;
} else {
return list.get(i);
}
}
public static <T> T left(List<T> list, int index, int offset) {
return HeapSort.child(list, index, offset, 1);
}
public static <T> T right(List<T> list, int index, int offset) {
return HeapSort.child(list, index, offset, 2);
}
/**
* 親ノードと子ノードを比較し、必要があれば入れ替える
* @param list 対象のリスト
* @param index ノードのインデックス
* @param offset 未ソート状態のリストの開始位置
* @param value 子ノードの値
* @param leaf 左か右か。1=左 2=右
* @param comp 比較関数
*/
public static <T> void swap(List<T> list, int index, int offset, T value, int leaf, Comparator<T> comp) {
if (value != null) {
if (comp.compare(list.get(index + offset), value) < 0) {
T tmp = list.get(index + offset);
list.set(index + offset, list.get(leaf + offset));
list.set(leaf + offset, tmp);
}
}
}
//sample
public static void main(String[] args) {
Integer[] l = new Integer[] { 5, 2, 104, 100, 6, 1, 7, 239, 2, 55 };
List<Integer> list = Arrays.asList(l);
HeapSort.sort(list, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
for (Integer r : list) {
System.out.println(r);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment