使用多个动态数组进行合并排序

Question

我一直在尝试创建 merge/mergesort 可以处理两个动态数组的函数。我一直在不断地输出内存位置而不是排序后的数字。我使用 break 尝试了多次，但仍然无法弄清楚出了什么问题。

template <class T>
void mergeSort(T list[], int lowerBound, int upperBound)
{
    if (lowerBound < upperBound)
    {
        int mid = (lowerBound + upperBound) / 2;
        cout << upperBound << lowerBound << endl;
        mergeSort(list, lowerBound, mid);
        cout << upperBound << lowerBound << endl;
        mergeSort(list, mid + 1, upperBound);
        merge(list, lowerBound, mid, upperBound);
    }
}

template <class T>
void merge(T list[], int lowerBound, int mid, int upperBound)
{
    int size1 = mid - lowerBound + 1;
    int size2 = upperBound - mid;

    T *tmp1 = new T[size1 + 1];
    T *tmp2 = new T[size2 + 1];

    for (int  i = 0; i < size1; i++)
    {
        tmp1[i] = list[lowerBound + i - 1];
        cout << "Here" << endl;
    }

    for (int i = 0; i < size1; i++)
    {
        tmp1[i] = list[lowerBound + i - 1];
        cout << tmp1[i] << endl;
    }
    system("pause");
    for (int j = 0; j < size2; j++)
    {
        tmp2[j] = list[mid + j];
    }

    tmp1[size1 + 1] = std::numeric_limits<int>::max();
    tmp1[size2 + 1] = std::numeric_limits<int>::max();

    int i = 1;
    int j = i;

    for (int k = lowerBound; k < upperBound; k++)
    {
        if (tmp1[i] <= tmp2[j])
        {
            list[k] = tmp1[i];
            i++;
        }
        else
        {
            list[k] = tmp2[j];
            j++;
        }
    }
}


int main()
{
    double myArray[7] = { 7, 6.4, 6.3, 8, 1, 2, 3 };
    for (int i = 0; i < 7; i++)
    {
        cout << myArray[i] << " ";
    }
    cout << endl;
    mergeSort(myArray, 0, 7);
    for (int i = 0; i < 7; i++)
    {
        cout << myArray[i] << " ";
    }
    return 0;
}

Answer 1

合并例程存在一些问题。一个问题是 size1 代表从 lowerBound 到 mid 的所有索引，包括 mid。这就是 mid - lowerBound + 1 的计算结果。我在评论中标记了其他 1 个错误。

我在思考这个实现的时候，用了一个小例子：

int lowerBound = 35, int mid = 37, int upperBound = 40

我建议使用这些值遍历代码，看看数学是否有意义。

template <class T>
void merge(T list[], int lowerBound, int mid, int upperBound)
{
    int size1 = mid - lowerBound + 1; // According to this, mid is 
                                      // part of the size1 array
    int size2 = upperBound - mid;
    T *tmp1 = new T[size1 + 1]; 
    T *tmp2 = new T[size2 + 1]; 

    for (int  i = 0; i < size1; i++)
    {
        tmp1[i] = list[lowerBound + i - 1]; // Remove - 1
        cout << "Here" << endl;
    }

    for (int i = 0; i < size1; i++) // This for loop is repeated, remove it
    {
        tmp1[i] = list[lowerBound + i - 1];
        cout << tmp1[i] << endl;
    }
    system("pause");
    for (int j = 0; j < size2; j++)
    {
        tmp2[j] = list[mid + j]; // Mid is not part of the size2 array
    }                            // Use mid + 1 + j (start at mid+1)

    tmp1[size1 + 1] = std::numeric_limits<int>::max(); // should be tmp1[size1]
    tmp1[size2 + 1] = std::numeric_limits<int>::max(); // should be tmp2[size2]; Also I couldn't tell if these are part of your debug statements, but I think you mean "tmp2"

    int i = 1; // This should start at 0
    int j = i; // This should start at 0

    for (int k = lowerBound; k < upperBound; k++) // Should be <=; upper
    {                                             // Bound is part of the
        if (tmp1[i] <= tmp2[j])                   // merge
        {
            list[k] = tmp1[i];
            i++;
        }
        else
        {
            list[k] = tmp2[j];
            j++;
        }
    }
}

使用多个动态数组进行合并排序

Merge sort using multiple dynamic arrays

c++

mergesort