JavaMerge

Aus ProgrammingWiki

Archivierte Version vom 2011-01-10T18:55:03+00:00. Aktuelle Version

Javabeispiel für Mergesort

private int[] a;
    private int[] b;    // Hilfsarray
    private int n;

    public void sort(int[] a)
    {
        this.a=a;
        n=a.length;
        // je nach Variante entweder/oder:
        b=new int[(n+1)/2];    b=new int[n];
        mergesort(0, n-1);
    }

    private void mergesort(int lo, int hi)
    {
        if (lo<hi)
        {
            int m=(lo+hi)/2;
            mergesort(lo, m);
            mergesort(m+1, hi);
            merge(lo, m, hi);
        }
    }

    
public void merge(int lo, int m, int hi)
{
    int i, j, k;

    i=0; j=lo;
    // vordere Hälfte von a in Hilfsarray b kopieren
    while (j<=m)
        b[i++]=a[j++];

    i=0; k=lo;
    // jeweils das nächstgrößte Element zurückkopieren
    while (k<j && j<=hi)
        if (b[i]<=a[j])
            a[k++]=b[i++];
        else
            a[k++]=a[j++];

    // Rest von b falls vorhanden zurückkopieren
    while (k<j)
        a[k++]=b[i++];
}

Quelle: FH-Flensburg

JavaMerge

Javabeispiel für Mergesort

Suche