Sortering datalister præsenterer en af de mere udfordrende problemer for edb-programmører , fordi det er svært at konceptualisere og gennemføre effektive sortering algoritmer programmeringssprog. Sorteringen kræver betydelig kopiering , flytning og læsning af data til at arbejde. Derfor programmører fokus på at udvikle effektive og generiske sortering algoritmer. En af disse, fletningen sortere , virker ved at dividere en liste over værdier igen og rekursivt til " del og hersk " problemet . Da merge slags er tænkt som en generisk løsning , de fleste sprog, herunder Java , har måder at gennemføre den. Flet Class
En sammenfletning slags tager en liste, der skal sorteres og rekursivt opdeler listen indtil den når enkelte værdier såsom enkelte numre . Den slags derefter rekombinerer tallene i sorteret orden , sidst vender tilbage en sorteret liste . En grundlæggende sortering klasse i Java , vil indeholde en liste til at sortere, og kalde en main flette sortering funktion det definerer : Hej
class Merge {
offentlig int [ ] x ;
public static void main ( String [] args ) {
x = [5 , 6, 3 , 4, 7, 8, 10, 2]
mergeSort (x, 0, x . længde -1 ),
}}
Merge Sort Function
uden for de vigtigste klasse vil opholde en sammenfletning slags funktion. Denne funktion segmenter en nummerserie for at sortere i listen. I første omgang vil dette interval repræsenterer hele listen , men da fletningen slags fortsætter , vil det tage kun halvdelen af listen indtil den når enkelte indgange . Derefter vil fletningen sortere funktionen kombinere elementerne i store lister , der er sorteret (Kilde 2 ) : Hej
public void mergeSort ( int lav , int hi ) {
hvis (lav < hi ) { int midten = (lav + hi ) /2; mergeSort (lav , middel ), mergeSort (i midten + 1 , hi ), merge (lav , middel , hi );}}
< br > Grundlæggende Merge Function
Merge-funktion vil kombinere to lister efter sortering dem. Hvis funktionen modtager enkelte elementer , vil det bestilte dem. Ellers vil det tage to separate lister , og afhængig af ønske om programmør bestille dem i stigende eller faldende rækkefølge:
private void merge ( int lav, int mid , int hi ) {
< p > int [ ] copy = new int [ x.length - 1]
//kopier begge dele ind hjælperen array for ( int i = lav, i < = hej , jeg + +) { copy [i ] = x [i] ;}
int i = lav, int j = mid + 1 , int k = lav , mens ( i < = midt && j <= hej ) {if ( copy [i] <= copy [ j] ) { x [ k] = copy [i ] i + +; } else {x [ k] = copy [ j] j + + ;} k + +; } //kopier resten af venstre side af array ind i målet vifte while ( i < = midt ) { x [ k] = copy [i] k + +; i + + ;}
}
< br > Flet Sort recurse
" mergeSort "-funktionen rekursivt opdeler listen. For det første opdeler den oprindelige liste i halvdelen for hver gang det kalder sig rekursivt . Når rekursionen når et enkelt ciffer , funktionen derefter Backtracks og begynder at bestille listen. Hver gang funktionen Backtracks til en tidligere funktion opkald , er det fusionerer to halvdele af en mindre liste , efterhånden arbejder tilbage til den fulde liste . "Flet "-funktionen synes at gøre det tunge løft ved at arrangere og kopiering værdier til listen, men i hjertet af en sammenfletning slags er i bedragerisk enkle " mergeSort "-funktion.
< Br >
