병합 정렬이란 Java의 병합 정렬에 대한 자세한 설명입니다.

병합 정렬의 Java 구현

병합 정렬(MERGE-SORT)은 병합 작업을 기반으로 하는 효과적인 정렬 알고리즘입니다. 이 알고리즘은 분할 및 정복 방법(pide 및 Conquer)의 매우 일반적인 예입니다. 애플리케이션. 이미 정렬된 하위 시퀀스를 병합하여 완전히 정렬된 시퀀스를 얻습니다. 즉, 먼저 각 하위 시퀀스를 순서대로 만든 다음 하위 시퀀스 세그먼트를 순서대로 만듭니다. 두 개의 순서 목록이 하나의 순서 목록으로 병합되는 경우 이를 양방향 병합이라고 합니다. 병합 프로세스는 다음과 같습니다. a[i]와 b[j]의 크기를 비교하고, a[i]≤b[j]인 경우 첫 번째 순서 목록의 a[i] 요소를 r[k]에 복사하고 추가합니다. 1을 i와 k에 각각 복사하고, 그렇지 않으면 두 번째 순서 목록의 요소 b[j]를 r[k]에 복사하고 j와 k에 각각 1을 추가하는 식으로 계속 진행합니다. 하나의 순서 목록을 가져온 후 나머지 다른 순서 목록의 요소는 아래 첨자 k에서 아래 첨자 t까지 r의 셀에 복사됩니다. 우리는 병합 정렬 알고리즘을 구현하기 위해 일반적으로 재귀를 사용합니다. 먼저 정렬할 간격 [s, t]를 중간점을 기준으로 2개로 나눈 다음 왼쪽 하위 범위를 정렬한 다음 오른쪽 하위 범위를 정렬합니다. 마지막으로 왼쪽 간격과 오른쪽 간격이 순서가 지정된 간격 [s,t]로 병합됩니다.

주요 두 가지 사항:

1 두 개의 정렬된 시퀀스를 하나의 정렬된 시퀀스로 병합하는 방법

2 이 두 시퀀스를 정렬된 시퀀스로 바꾸는 방법

첫 번째 문제 해결:

주문한 두 계열을 병합하는 방법. 이는 매우 간단합니다. 두 시퀀스의 첫 번째 숫자를 비교하여 더 작은 숫자를 먼저 취한 후 해당 시퀀스의 숫자를 삭제하면 됩니다. 그런 다음 열 중 하나가 비어 있으면 다른 열의 데이터를 하나씩 꺼내십시오.

public static void merge(int[] nums, int low, int mid, int high) {  
        int[] temp = new int[high - low + 1];  
        int i = low;// 左指针  
        int j = mid + 1;// 右指针  
        int k = 0;  
  
        // 把较小的数先移到新数组中  
        while (i <= mid && j <= high) {  
            if (nums[i] < nums[j]) {  
                temp[k++] = nums[i++];  
            } else {  
                temp[k++] = nums[j++];  
            }  
        }  
  
        // 把左边剩余的数移入数组  
        while (i <= mid) {  
            temp[k++] = nums[i++];  
        }  
  
        // 把右边边剩余的数移入数组  
        while (j <= high) {  
            temp[k++] = nums[j++];  
        }  
  
        // 把新数组中的数覆盖nums数组  
        for (int k2 = 0; k2 < temp.length; k2++) {  
            nums[k2 + low] = temp[k2];  
        }  
    }

두 번째 질문: 그룹 A와 B는 두 그룹으로 나눌 수 있습니다. 비유하자면, 분리된 그룹에 하나의 데이터만 있는 경우 그룹이 순서에 도달한 것으로 간주하고 인접한 두 그룹을 병합할 수 있습니다. 이런 방식으로 병합 정렬은 먼저 배열을 재귀적으로 분해한 다음 배열을 병합하여 완료됩니다.

public static int[] sort(int[] nums, int low, int high) {  
        int mid = (low + high) / 2;  
        if (low < high) {  
            // 左边  
            sort(nums, low, mid);  
            // 右边  
            sort(nums, mid + 1, high);  
            // 左右归并  
            merge(nums, low, mid, high);  
        }  
        return nums;  
    }

전체 코드:

package algorithm;import java.util.Arrays;public class MergeSort {	  public static int[] sort(int[] nums, int low, int high) {  
	        int mid = (low + high) / 2;  
	        if (low < high) {  
	              
	            sort(nums, low, mid);  
	             
	            sort(nums, mid + 1, high);  
	             
	            merge(nums, low, mid, high);  
	        }  
	        return nums;  
	    }  
	  
	    public static void merge(int[] nums, int low, int mid, int high) {  
	        int[] temp = new int[high - low + 1];  
	        int i = low;	        int j = mid + 1;  
	        int k = 0;  
	  
	        while (i <= mid && j <= high) {  
	            if (nums[i] < nums[j]) {  
	                temp[k++] = nums[i++];  
	            } else {  
	                temp[k++] = nums[j++];  
	            }  
	        }  
	  
	      
	        while (i <= mid) {  
	            temp[k++] = nums[i++];  
	        }  
	  
	      
	        while (j <= high) {  
	            temp[k++] = nums[j++];  
	        }  
	  
	        
	        for (int k2 = 0; k2 < temp.length; k2++) {  
	            nums[k2 + low] = temp[k2];  
	        }  
	    }  
	public static void main(String[] args) {		  int[] nums = { 29, 78, 800, 3, 551, 6, 97, 0, 5, 4 };  
		  
	        MergeSort.sort(nums, 0, nums.length-1);  
	        System.out.println(Arrays.toString(nums));  
	}

}

위 내용은 병합 정렬이란 Java의 병합 정렬에 대한 자세한 설명입니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!