Hvordan Flett en Sorter i Python

Sortering lister av data er et problem som har plaget programmerere siden begynnelsen av programmering. Sortering noen liste over data kan ende opp som en minne- og tidkrevende oppgave. På grunn av dette, har ulike sorteringsmetoder blitt oppfunnet for å minimere utfordringen og krefter på å sortere. En metode er fusjonere sortering. Det subdivides en liste rekursivt i entall elementer og rekombinerer listen i sortert form. Alle programmeringsspråk som støtter rekursjon, som Python, kan gjennomføre en sammenslåing slag.

Bruksanvisning

1 Å definere "mergeSort" -funksjon. Denne grunnleggende funksjon kaller seg rekursivt, splitte listestørrelsen i to med hver samtale. Når mergeSort funksjon treff en liste med ett element, stopper rekursjon og element avkastning. Som mergeSort rekursjon unwinds er hver mindre liste flettet sammen i sortert rekkefølge. Dette eksemplet viser en enkel mergeSort funksjon som tar en liste som argument:

def mergeSort (li):

. . . hvis len (li) <2:

. . . avkastning li

. . . mid = len (li) / 2

. . . først = mergeSort (li [: mid])

. . . siste = mergeSort (li [mid:])

. . . avkastning merge (først, sist)

2 Sett opp flettingen metoden. Denne funksjonen vil fungere som sortering metoden; den gir en sortert liste av elementer. Flettingen metoden tar to allerede sortert lister. Den definerer deretter en intern liste "sortert" som skal representere de samlede sorterte argumentlister. Flettingen metoden oppnår dette ved å ta det minste elementet og sette det inn i en ny liste "sortert". Når en av listene er ferdig, er den andre listen er satt inn i sin helhet.

def flette (x, y):

. . . sortert = []

3 Flett listene i flettingen metoden. Den "mens" loop i eksempelet sammen hvert listepunkt ved element, tar det minste elementet og sette det inn i en ny liste "sortert". Når en av listene er ferdig, er den andre listen er satt inn i sin helhet, og det nye sortert liste returneres:

. . . i, j = 0, 0-

. . . mens jeg <len (x) og j <len (y):

. . . hvis x [i] <= y [J]:

. . . sorted.append (x [i])

. . . i + = 1

. . . ellers:

. . . sorted.append (y [j])

. . . j + = 1

. . . sortert + = x [I:]

. . . sortert + = y [: j]

. . . tilbake sortert