Java 정렬 알고리즘 (3) - 병합 정렬 (MergeSort) 재 귀 와 비 재 귀 구현

병합 에는 재 귀 와 비 재 귀 두 가지 가 있다.
병합 의 사상 은 다음 과 같다. 1. 원수 조 를 먼저 두 개의 요 소 를 한 조 로 정렬 한 다음 에 네 개의 한 조, 여덟 개의 한 조로 합 쳐 전체 수 조 를 합병 할 때 까지 한다.2. 두 개의 키 배열 을 합병 할 때 임시 배열 을 통 해 현재 의 병합 후의 두 배열 을 저장 해 야 합 니 다.3. 임시 배열 을 원래 배열 에 대응 하 는 위치 로 복사 합 니 다.
재 귀적 이지 않 은 코드 는 다음 과 같 습 니 다.

package mergesort;

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
//          
public class MergeSort{
    public static void main(String args[]){
        MergeSort mer = new MergeSort();
        int[] array = mer.getArray();
        System.out.println("OriginalArray:" + Arrays.toString(array));
        mer.mergeSort(array);
        System.out.println("SortedArray:" + Arrays.toString(array));
    }
    public int[] getArray(){
        Scanner cin = new Scanner(System.in);
        System.out.print("Input the length of Array:");
        int length = cin.nextInt();
        int[] arr = new int[length];
        Random r = new Random();
        for(int i = 0; i < length; i++){
            arr[i] = r.nextInt(100);
        }
        cin.close();
        return arr;
    }
    public void mergeSort(int[] a){
        int len = 1;
        while(len < a.length){
            for(int i = 0; i < a.length; i += 2*len){
                merge(a, i, len);
            }
            len *= 2;
        }
    }

    public void merge(int[] a, int i, int len){
        int start = i;
        int len_i = i + len;//         
        int j = i + len;
        int len_j = j +len;//         
        int[] temp = new int[2*len];
        int count = 0;
        while(i < len_i && j < len_j && j < a.length){
            if(a[i] <= a[j]){
                temp[count++] = a[i++];
            }
            else{
                temp[count++] = a[j++];
            }
        }
        while(i < len_i && i < a.length){//  ：  i          
            temp[count++] = a[i++];
        }
        while(j < len_j && j < a.length){
            temp[count++] = a[j++];
        }
        count = 0;
        while(start < j && start < a.length){
            a[start++] = temp[count++];
        }
    }
}

귀속 알고리즘 의 실현 코드 는 다음 과 같다.

package mergesort;

public class MergeSort {
    public static void mergeSort(int[] data,int left,int right){ //left,right        
        if(leftint half=(left+right)/2;
            mergeSort(data,left,half);
            mergeSort(data,half+1,right);
            merge(data,left,right);
        }
    }
    public static void merge(int []a,int l,int h){
        int mid=(l+h)/2;
        int i=l;
        int j=mid+1;
        int count=0;
        int temp[]=new int[h-l+1];
        while(i<=mid&&j<=h){
            if(a[i]else{
temp[count++]=a[j++];
}        
}
while(i<=mid){
temp[count++]=a[i++];
}
while(j<=h){
temp[count++]=a[j++];
}
count=0;
while(l<=h){
a[l++]=temp[count++];
}
}
public static void printArray(int arr[]){
for(int k=0;kout.print(arr[k]+"\t");
}
}
public static int[] getArray(){
//      int[] data={4,2,3,1};
int[] data={543,23,45,65,76,1,456,7,77,88,3,9};
return data;
}
public static void main(String args[]){
int[]a=getArray();
System. out. print ("배열 정렬 전:");
printArray(a);
System.out.print("");
mergeSort(a,0,a.length-1);
System. out. print ("정렬 후:");
printArray(a);
}
}

정렬 을 병합 하 는 시간 복잡 도 는 O (n * log2n) 이 고 공간 복잡 도 는 O (n) 이다.
병합 정렬 은 안정 적 인 정렬 방법 이다.