Lijsten sorteren van gegevens vormt een van de meer uitdagende problemen voor computerprogrammeurs , want het is moeilijk te conceptualiseren en implementeren van efficiënte sorteeralgoritmes in programmeertalen . Sortering vereist aanzienlijke kopiëren , verplaatsen en het lezen van de gegevens te werken . Dienovereenkomstig , programmeurs richten op de ontwikkeling van efficiënte en generieke sortering algoritmes . Een van deze , de merge sort , werkt door het verdelen van een lijst met waarden over en recursief om " verdeel en heers " het probleem . Omdat merge sort is bedoeld als een generieke oplossing , de meeste talen , waaronder Java , moeten manieren om het te implementeren . Samenvoegen Class
Een merge sort neemt een lijst te worden gesorteerd en recursief splitst de lijst tot aan enkele waarden , zoals enkele nummers . Het soort recombineert vervolgens de nummers in gesorteerde volgorde , eventueel terugsturen van een gesorteerde lijst . Een basis sortering klasse in Java zal een lijst een belangrijke samenvoegen sorteerfunctie het definieert bevatten voor het sorteren , en bel :
Merge class { public int
[ ] x ;
public static void main ( String [ ] args ) {
x = [ 5 , 6 , 3 , 4 , 7 , 8 , 10 , 2 ] ; mergesort
( x , 0 , x . lengte - 1 ) ;
} }
Merge Sort functie
Buiten de hoofdklasse zal een merge sorteerfunctie wonen . Deze functie segmenten een nummerreeks te sorteren in de lijst . In eerste instantie zal dit bereik de hele lijst te vertegenwoordigen , maar als het merge sort blijft , zal het slechts de helft van de lijst nemen tot aan enkele inzendingen . Dan zal de merge sorteerfunctie recombineren de elementen in grote lijsten die zijn gesorteerd ( Bron 2 ) : public void mergesort
( int laag , int hi ) {
if ( laag < hi ) {int midden = ( laag + hi ) /2 ; mergesort ( laag , midden) ; mergesort ( midden + 1 , hi ) , samenvoegen ( laag , midden, hi ) ; } }
< br > Basic Merge functie
De merge -functie zal twee lijsten te combineren na sortering hen. Als de functie ontvangt enkele elementen , zal het hen bestellen . Anders zal het twee aparte lijsten te nemen , en afhankelijk van de wens van de programmeur om ze in oplopende of aflopende volgorde : private void merge ( int laag , int midden , int hi ) op {
int [ ] copy = new int [ gelijk aan x.length - 1 ] ;
//Kopieer beide onderdelen in de helper array voor ( int i = laag ; i < = hi ; i + + ) { copy [ i ] = x [ i ] ; }
int i = laag ; int j = midden + 1 ; int k = laag ; while ( i < = midden && j < = hi ) {if ( copy [ i ] < = copy [ j ] ) { x [ k ] = copy [ i ] ; i + + ; } else { x [ k ] = copy [ j ] ; j + + ; } k + + ; } //Kopieer de rest van de linkerkant van de matrix in het doel -array while ( i < = midden ) { x [ k ] = copy [ i ] ; k + + ; i + + ; } }
< br > samenvoegen Sorteren Recurse
de functie " mergesort " recursief splitst de lijst . Ten eerste , het verdeelt de oorspronkelijke lijst in de helft voor elke keer dat noemt zichzelf recursief . Als de recursie een cijfer bereikt , de functie Backtracks vervolgens en begint aan de lijst te bestellen . Elke keer dat de functie Backtracks naar een vorige functie aan te roepen , het voegt twee helften van een kleinere lijst , uiteindelijk terug te werken naar de volledige lijst . De functie " merge " lijkt het zware werk te doen door het organiseren en kopiëren waarden in de lijst , maar het hart van een merge soort is in de bedrieglijk eenvoudige functie " mergesort " .
< Br >
|
