Heapsort in Java

Hier eine Implementierung von Heapsort in Java:

package at.ande.sorting.heapsort;

import java.util.ArrayList;

public class HeapSort {
 
 ArrayList list;
 int length;
 
 public ArrayList start(ArrayList arraylist){
  list = arraylist;
  length = list.size();
  createHeap();
  while(length > 1){
   length--;
   change(0, length);
   downheap(0);
  }
  return list;
 }
 
 public void createHeap(){
  for (int i = length / 2 - 1; i >= 0; i--){
   downheap(i);
  }
 }
 
 public void downheap(int i){
  int j = 2 * i + 1;
  while (j < length){
   if(j + 1 < length && list.get(j + 1) > list.get(j)){
    j++;
   }
   if(list.get(i) > list.get(j)){
    break;
   }
   change(i, j);
   i = j;
   j = 2 * i + 1;
  }
 }
 
 public void change(int i, int j){
  int temp = list.get(i);
  list.set(i, list.get(j));
  list.set(j, temp);
 }
}

Im Vergleich zu den auch in diesem Blog implementieren Sortieralgorithmen schneidet Heapsort ganz gut ab:

List Area: 0 - 999
List Numbers: 100000
Unsorted List:
- Iterative Quicksort: 123 ms
- Bubblesort: 45787 ms
- Gnomesort: 75418 ms
- Heapsort: 103 ms
Sorted List:
- Iterative Quicksort: 1518 ms
- Bubblesort: 5 ms
- Gnomesort: 8 ms
- Heapsort: 49 ms

Links:
Wikipediaeintrag über Heapsort
Ausführlicher Artikel der Uni Flensburg über Heapsort