合併排序實現洗牌陣列但不排序

Question

我是一名初學者程序員。這是我在Java中實現的MergeSort算法。 我似乎無法修復這個錯誤。

數組被洗牌但未被排序。有人能指出我的錯嗎？

public static int[] divide(int a[], int n, int low, int high) { 
    if (low == high) { 
    int[] b = { a[low] }; 
    return b; 
    } 
    int mid = (low + high)/2; 

    divide(a, n/2, low, mid); 
    divide(a, n/2, mid + 1, high); 
    return conquer(a, low, mid, high); 
} 

public static int[] conquer(int a[], int low, int mid, int high) { 
    int p = low; 
    int q = mid + 1; 
    int[] sorted = new int[high - low + 1]; 
    int current = 0; 
    while (p <= mid && q <= high) { 
    if (a[p] < a[q]) { 
     sorted[current++] = a[p++]; 
    } else 
     sorted[current++] = a[q++]; 
    } 
    if (p <= mid) { 
    while (p <= mid) { 
     sorted[current++] = a[p++]; 
    } 
    } 
    if (q <= high) { 
    while (q <= high) { 
     sorted[current++] = a[q++]; 
    } 
    } 

    return sorted; 
} 

Answer 1

主要問題是您調用divide而不是使用返回值（排序的子數組）。 既然你沒有使用中期結果，當你打電話征服時，它並不是真正的「征服」。

它可以固定如下：

public static int[] divide(int a[], int low, int high) { 
    if (low == high) { 
     int[] b = { a[low] }; 
     return b; 
    } 
    int mid = (low + high)/2; 

    int[] lower = divide(a, low, mid); 
    int[] higher = divide(a, mid + 1, high); 
    return conquer(lower, higher); 
} 

public static int[] conquer(int[] low, int[] high) { 
    int p = 0; 
    int q = 0; 
    int[] sorted = new int[high.length + low.length]; 
    int current = 0; 
    while (p < low.length && q < high.length) { 
     if (low[p] <= high[q]) { 
      sorted[current++] = low[p++]; 
     } else 
      sorted[current++] = high[q++]; 
    } 
    while (p <= low.length-1) { 
     sorted[current++] = low[p++]; 
    } 
    while (q <= high.length-1) { 
     sorted[current++] = high[q++]; 
    } 
    return sorted; 
} 

使用代碼：

int[] a = {3,1,2}; 
a = divide(a, 0, 2); 
System.out.println(Arrays.toString(a)); 

打印：

[1, 2, 3]