0

我被困在这种合并排序方法上。我不想递归地做，但我不能让这个为我工作。我认为需要做一个小的改变才能让它发挥作用。有什么建议么？ 

  protected static void merge(long[] a, long[] workSpace, int lowPtr, int highPtr, int upperBound) {
    int j = 0;                             // workspace index
    int lowerBound = lowPtr;
    int mid = highPtr-1;
    int n = upperBound-lowerBound+1;       // # of items

    while(lowPtr <= mid && highPtr <= upperBound)
        if(a[lowPtr] < a[highPtr] )
            workSpace[j++] = a[lowPtr++];
        else
            workSpace[j++] = a[highPtr++];

    while(lowPtr <= mid)
        workSpace[j++] = a[lowPtr++];

    while(highPtr <= upperBound)
        workSpace[j++] = a[highPtr++];

    for(j=0; j<n; j++)
        a[lowerBound+j] = workSpace[j];
4

1 回答 1

0

我怀疑这与您如何在外部使用此例程有关。盯着它看了 5 分钟后我看不到错误，所以我测试了它，它似乎工作正常。

你不需要知道 c++（我碰巧在这台机器上有一个方便的编译器）

int main() {
    long a[10] = {1,2,3,4,15,5,11,12,13,14}; // two sorted halves to merge
    long * temp = new long[10];
    for (int i = 0; i < 10; i++)
    {
        cout << a[i] << ","; // printout before merge
    }
    cout << endl;
    merge(a, temp, 0, 5, 9); // 0-4 and 5-9
    for (int i = 0; i < 10; i++)
    {
        cout << a[i] << ","; // printout after merge
    }
}

输出：

1,2,3,4,15,5,11,12,13,14,
1,2,3,4,5,11,12,13,14,15,

更多输出只是为了说服您：

1,2,6,14,15,5,11,12,32,100,
1,2,5,6,11,12,14,15,32,100,

1,2,100,143,1500,5,112,121,320,1000,
1,2,5,100,112,121,143,320,1000,1500,

12,20,100,143,179,5,12,121,320,430,
5,12,12,20,100,121,143,179,320,430,
于 2014-02-11T08:26:42.707 回答