今回はヒープソートを紹介します。
ヒープソートとはその名のとおり、ヒープ構造を用いてソートを行うアルゴリズムです。
ヒープ構造とは2分木構造の一種で、ルートが常にそのヒープ構造の中の最大値(あるいは最小値）を指すように調整を行うデータ構造です。
このヒープ構造にソートを行いたいデータを追加していき、次にルートからデータを取り出して順番に並べていきます。

sort/HeapSort.java

package sort;

 import java.util.List;
 import java.util.ArrayList;
 import java.util.Collections;

 public class HeapSort {

   private static <E extends Comparable<E>> void swap(List<E> list, int a, int b) {
     E tmp = list.get(a);
     list.set(a, list.get(b));
     list.set(b, tmp);
   }

   private static <E extends Comparable<E>> void insertHeap(List<E> list, int i) {
     for (int j = (i - 1) / 2; i > 0; i = j, j = (i - 1) / 2) {
       if (list.get(i).compareTo(list.get(j)) > 0) {
     swap(list, i, j);
       } else {
     return;
       }
     }
   }

   private static <E extends Comparable<E>> void deleteHeap(List<E> list, int i) {
     swap(list, 0, i--);
     int k;
     for (int j = 0; j < i; j = k) {
       int l = j * 2 + 1;
       int r = l + 1;
       if (l > i) {
     return;
       }
       k = l;
       if (l < i) {
     k = (list.get(l).compareTo(list.get(r)) > 0) ? l : r;
       }
       swap(list, j, k);
     }
     insertHeap(list, i);
   }

   public static <E extends Comparable<E>> void sort(List<E> list) {
     for (int i = 1; i < list.size(); i++) {
       insertHeap(list, i);
     }
     for (int i = list.size() - 1; i >= 1; i--) {
       deleteHeap(list, i);
     }
   }

   public static void main(String args[]) {
     List<Integer> list = new ArrayList<Integer>();
     for (int i = 0; i < 10; i++) {
       list.add(i);
     }
     Collections.shuffle(list);
     System.out.println(list);
     sort(list);
     System.out.println(list);
   }
 }