マージソートとは Javaのマージソートについて詳しく説明します。

Java はマージ ソートを実装します

マージ ソート (MERGE-SORT) は、マージ操作に基づく効果的なソート アルゴリズムです。このアルゴリズムは、分割統治法 (pide と Conquer) を使用する非常に典型的なアプリケーションです。すでに順序付けされているサブシーケンスをマージして、完全に順序付けされたシーケンスを取得します。つまり、まず各サブシーケンスを順序どおりにしてから、サブシーケンス セグメントを順序どおりにします。 2 つの順序付きリストが 1 つの順序付きリストにマージされる場合、それは双方向マージと呼ばれます。 マージ プロセスは次のとおりです。 a[i] と b[j] のサイズを比較し、 a[i]≤b[j] の場合、最初の順序付きリストの要素 a[i] を r[k] にコピーし、次の値を追加します。それ以外の場合は、2 番目の順序付きリストの要素 b[j] を r[k] にコピーし、j と k にそれぞれ 1 を加算するというように、1 つの順序付きリストがフェッチされるまで続きます。もう一方の順序付きリストの要素は、添え字 k から添え字 t までの r のセルにコピーされます。通常、再帰を使用してマージ ソート アルゴリズムを実装します。まず、ソート対象の区間 [s, t] を中間点で 2 つに分割し、次に左側のサブ範囲をソートし、次に右側のサブ範囲をソートし、最後に を使用します。左側の間隔と右側の間隔の間のマージ操作。順序付けされた間隔 [s,t] にマージします。

主な 2 つのポイント:

1 2 つの順序付きシーケンスを 1 つの順序付きシーケンスにマージする方法

2 これら 2 つのシーケンスを順序付きシーケンスに変換する方法

最初の問題を解決する:

マージする方法 2 つの順序付きシーケンスをマージします。これは非常に簡単です。2 つのシーケンスの最初の番号を比較し、小さい方を最初に取得した後、対応するシーケンスの番号を削除します。次に、それらを比較します。一方の列が空の場合は、もう一方の列のデータを 1 つずつ取り出します。

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];  
        }  
    }

2 番目の質問: グループ A と B は 2 つのグループに分けることができます。類推により、分離されたグループにデータが 1 つだけある場合、そのグループは秩序に達したとみなして、隣接する 2 つのグループをマージできます。このように、マージ ソートは、まず配列を再帰的に分解し、次に配列をマージすることで完了します。

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 中国語 Web サイトの他の関連記事を参照してください。