褰掑苟鎺掑簭绠楁硶鐨勫疄鐜版楠ゅ涓嬶細

1. 棣栧厛锛屽疄鐜颁竴涓綊骞舵搷浣滃嚱鏁般€傝鍑芥暟灏嗕袱涓凡鎺掑簭鐨勬暟缁勫悎骞朵负涓€涓柊鐨勫凡鎺掑簭鐨勬暟缁勩€備緥濡傦細

public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; ++i) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; ++j) {
R[j] = arr[mid + 1 + j];
}
int i = 0, j = 0;
int 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++;
}
}

2. 鐒跺悗锛屽疄鐜板綊骞舵帓搴忓嚱鏁般€傝鍑芥暟灏嗘暟缁勫垎鎴愪袱鍗婏紝瀵规瘡涓€鍗婅繘琛岄€掑綊璋冪敤褰掑苟鎺掑簭鍑芥暟锛屾渶鍚庡悎骞朵袱涓凡鎺掑簭鐨勬暟缁勩€備緥濡傦細

public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}

3. 鏈€鍚庯紝璋冪敤褰掑苟鎺掑簭鍑芥暟瀵规暣涓暟缁勮繘琛屾帓搴忋€備緥濡傦細

int[] arr = {5, 2, 8, 3, 1, 9, 4, 6, 7};
mergeSort(arr, 0, arr.length - 1);

杩欐牱锛屾暟缁刟rr灏嗕細琚綊骞舵帓搴忕畻娉曟帓搴忋€?/p>