Was ist Zusammenführungssortierung?
Die Zusammenführungssortierung verwendet Rekursions- und Divide-and-Conquer-Techniken, um die Datensequenz in immer kleinere halbe Untertabellen zu unterteilen, dann die halben Untertabellen zu sortieren und schließlich rekursive Methoden zum Sortieren der sortierten halben Untertabellen zu verwenden -Tabellen verschmelzen zu immer größeren geordneten Sequenzen.
Kernidee
Zwei geordnete Sequenzen zu einer großen geordneten Sequenz zusammenführen. Durch Rekursion werden Ebenen zusammengeführt, was als Zusammenführen bezeichnet wird.
(Empfohlenes Tutorial: Java-Schnellstart)
Implementierungscode:
import java.util.Arrays; /** * @author god-jiang * @date 2020/1/13 */ //归并排序,时间复杂度为O(N*logN),空间复杂度为O(N) public class MergeSort { public static void MergeSort(int[] arr, int start, int end) { //分治的结束条件 if (start >= end) { return; } //保证不溢出取start和end的中位数 int mid = start + ((end - start) >> 1); //递归排序并且合并 MergeSort(arr, start, mid); MergeSort(arr, mid + 1, end); Merge(arr, start, mid, end); } //合并 public static void Merge(int[] arr, int start, int mid, int end) { int[] temp = new int[end - start + 1]; int p1 = start; int p2 = mid + 1; int p = 0; while (p1 <= mid && p2 <= end) { if (arr[p1] > arr[p2]) { temp[p++] = arr[p2++]; } else { temp[p++] = arr[p1++]; } } while (p1 <= mid) { temp[p++] = arr[p1++]; } while (p2 <= end) { temp[p++] = arr[p2++]; } for (int i = 0; i < temp.length; i++) { arr[i + start] = temp[i]; } } public static void main(String[] args) { int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5}; MergeSort(a, 0, a.length - 1); System.out.println(Arrays.toString(a)); } }
Laufendes Ergebnis:
Empfohlene verwandte Video-Tutorials: Java-Video-Tutorial
Das obige ist der detaillierte Inhalt vonSo implementieren Sie die Zusammenführungssortierung mit Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!