Java 병합정렬 구현

1 개요[ | ]

Java 병합정렬 구현
자바 병합정렬 구현
Java
Copy
public class MyClass {
    static void merge(int[] arr, int left, int middle, int right) {
        int n1 = middle - left + 1;
        int n2 = right - middle;
        int L[] = new int[n1];
        int R[] = new int[n2];
        int i, j, k;
        for(i=0; i<n1; ++i) L[i]=arr[left+i];
        for(j=0; j<n2; ++j) R[j]=arr[middle+j+1];
        i=0; j=0; k=left;
        while( i<n1 && j<n2) {
            if(L[i] <= R[j]) { arr[k] = L[i]; i++; }
            else { arr[k] = R[j]; j++; }
            k++;
        }
        while( i < n1 ) { arr[k] = L[i]; i++; k++; }
        while( j < n2 ) { arr[k] = R[j]; j++; k++; }
    }
    static void merge_sort(int arr[], int left, int right) {
        if(left >= right) return;
        int middle = (left+right)/2;
        merge_sort(arr, left, middle);
        merge_sort(arr , middle+1, right);
        merge(arr, left, middle, right);
    }
    public static void main(String args[]) {
        int[] arr = {9,1,22,4,0,-1,1,22,100,10};
        merge_sort(arr, 0, arr.length-1);
        for(int x: arr) System.out.format("%d ",x);
        // -1 0 1 1 4 9 10 22 22 100 
    }
}
2 같이 보기[ | ]
