The heapsort algoritmen är en av de snabbast sorteringsalgoritmer tillgängliga . Programmerare använder heapsort i Java eftersom det är ett bra val för mycket stora matriser som de vet är i en osorterad tillstånd . För effektivitet skull , är en verklig trädstruktur används inte . Istället är trädet bildas på plats , höger i arrayen. Den heapsort algoritmen är en " på plats " -algoritmen , eftersom den inte kräver någon extra minne för att utföra sorteringen . Instruktioner
1
Komponera swap metoden . Detta kommer att byta två element i en array " " public static void swap ( int [ ] a , int i , int j ) { int tmp = a [ j ] ; . A [ j ] = a [ i] ; a [ i] = tmp ; } " "
2
Skriv kärnan i algoritmen , den siftDown metoden . Den används till både form högen struktur och göra själva sorteringen.
3
undersöka stora värden till roten av trädet och små värden mot bladen med siftDown metoden . Eftersom denna metod anropas flera gånger under sorteringsprocessen , är den största noden konsekvent siktas till rotnoden och flyttas till slutet av arrayen . Varje nod n har upp till två barn, vars index är n * 2 + 1 och n * 2 + 2 . " " public static void siftDown ( int [ ] a , int start , int end ) { int root = start , medan ( root * 2 + 1 int barn = rot * 2 + 1 , //Om barnet har ett syskon och barnets värde är lägre än dess syskon om ( barn barn + + ; } if ( a [ root ] swap ( a , rot , barn ) , root = barn ; } else {return ;} } } " "
4
Använd heapify metoden . metoden kallas i början av det slag att skapa den första högen struktur . Detta görs snabbt , eftersom högen struktur är något vagt . det enda kravet är att varje rot nod måste vara större än den underordnade noder " " public static void heapify ( int [ ] a ) {for ( int start = a.length /2 - 1 , start > = 0; start - ) . siftDown ( a , start , a.length - 1 ) ; } " "
5
Skriv heapSort den metod först heapifies arrayen för att förbereda sig för den typ den siftDown metoden kallas då igen eftersom rotnoden är nu ett litet värde här . . . sållar ett nytt stort värde till roten noden , och hela processen upprepas tills storleken på högen är en " " public static void heapSort ( int [ ] a ) { heapify ( a ) , . for ( int slut = a . längd - 1 , end > 1 , end - ) { swap ( a , slutet , 0 ) ; siftDown ( a , 0 , slut - 1 ) ;} } " "
6
Test . den heapSort metoden följande exempel visar ett litet testprogram " " public static void main ( String [] args ) { int [ ] a = new int [ 10 ] ; . for ( int i = 0; jag for (int i = 0 , jag swap ( a , i, i + ( int ) ( Math.random ( ) * ( 9 - i) ) ) , System.out.println ( " Innan sortering : " ) ; for (int i = 0 ; jag heapSort ( a ) , System.out.println ( " efter sortering " ) , for (int i = 0 ; i} " " Addera
