Sortering datalistor presenterar en av de mer utmanande problem för programmerare , eftersom det är svårt att konceptualisera och implementera effektiva sorteringsalgoritmer i programspråk . Sortering kräver betydande kopiera, flytta och läsning av data att arbeta . Följaktligen programmerare fokusera på att utveckla effektiva och generiska sorteringsalgoritmer . En av dessa , den merge sort , fungerar genom att dividera en lista med värden över och över rekursivt att " söndra och härska " problemet . Eftersom merge sort är avsedd som en generisk lösning , de flesta språk, inklusive Java , har sätt att genomföra den . Merge Klass
En sammanfogning sort tar en lista som ska sorteras och rekursivt delar upp listan tills nå enskilda värden , såsom enskilda siffror . Sorteringen rekombinerar sedan siffrorna i sorterad ordning , så småningom återvänder en sorterad lista . En grundläggande sortering klass i Java kommer att innehålla en lista för att sortera, och ringa ett huvud sammanfogning sorteringsfunktion den definierar :
class Merge {
public int [ ] x ;
public void main (String [] args ) {
x = [ 5 , 6 , 3 , 4 , 7 , 8 , 10 , 2 ] ;
mergesort (x, 0 , x . längd - 1 ) ;
} } Addera Merge sort funktion
Utanför huvudklassen kommer att bo en merge sort funktion . Denna funktion segment en nummerserie för att sortera i listan . Inledningsvis kommer detta intervall representerar hela listan , men eftersom sammanfogningen Sortera fortsätter , tar det bara hälften av listan tills nå enstaka poster . Då kommer sammanslagningen sorteringsfunktion rekombinera elementen till stora listor som sorteras (Källa 2 ) :
public void mergesort ( int lite , int hi ) {
om ( låg < hi ) { int mitten = ( låg + hi ) /2 ; mergesort ( låg , mitten ) , mergesort ( mitten + 1 , hi ) , merge ( låg , mitten , hi ) ; } } Addera
Grundläggande Merge Function
merge -funktionen kommer att kombinera två listor efter sortering . Om funktionen tar emot enskilda element , kommer det att beställa dem . Annars kommer det att ta två separata listor , och beroende på önskan av programmeraren för dem i stigande eller fallande ordning :
private void merge (int låga , int mitten , int hi ) {
int [ ] Copy = new int [ x.length - 1 ] ;
//Kopiera båda delarna till figuranten arrayen for ( int i = låg , i < = hej , jag + + ) { kopia [i ] = x [ i] ; }
int i = låg , int j = mitten + 1 , int k = låg , medan ( i < = mitt && j < = hi ) {if (kopiera [ i] < = Kopiera [ j ] ) { x [ k ] = kopia [ i] ; i + + ; } else { x [ k ] = kopia [ j ] ; j + + ; } k + + ; } //Kopiera resten av den vänstra sidan av gruppen i börvärdesuppsättning while (i < = mitten ) { x [ k ] = kopia [ i] , k + + , jag + + ; }
}
Merge Sort Recurse
" mergesort " -funktionen delar rekursivt listan . Först , delar upp den ursprungliga listan i hälften för varje gång det kallar sig rekursivt . När rekursion når en enda siffra , backtracks funktionen då och börjar beställa listan . Varje gång funktionen Backtracks till en tidigare funktion samtal , slår samman det två halvor av en mindre lista , så småningom arbeta tillbaka till hela listan . Den " merge " funktionen verkar göra grovjobbet genom att arrangera och kopiera värden i listan , men mitt i en sammanslagning sort är i bedrägligt enkla " mergesort " funktionen .
