我正在尝试使用 class 中的数组实现合并排序，但我得到的只是随机值，大部分为零

Question

我不知道我是否可以在我的阵列上这样操作，或者我应该创建它的一些副本。我还有其他算法可以实现，这就是为什么我想到在此 class 中使用数组。我认为问题在于使用这个数组 ,arr"，因为当我在 separate_and_merge 函数中打印值时，它们大部分是 0，或者是垃圾，我不知道我做错了什么。

#include <iostream>

template<typename TYPE, int SIZE>
class Array
{
private:
    TYPE* arr;
public:
    void DisplayArray();
    void separate_and_merge(int begin, int middle, int end);
    void merge_sorting(int begin, int end);
    void getRandomArray();
    Array();
};

template<typename TYPE, int SIZE>
Array<TYPE, SIZE>::Array()
{
    arr = new TYPE[SIZE];
}

template<typename TYPE, int SIZE>
void Array<TYPE, SIZE>::separate_and_merge(int begin, int middle, int end)
{

    int size_left = middle - begin + 1; //rozmair lewej podtablicy
    int size_right = end - middle; // rozmiar prawej podtablicy


    TYPE arr1[size_left]; // inicjacja tablic
    TYPE arr2[size_right];

    // podpisanie wartosci pod tablice
    for (int i = 0; i < size_left; i++)
    {
        arr1[i] = arr[i];
    }

    for (int j = 0; j < size_right; j++)
    {
        arr2[j] = arr[j + middle + 1];
    }

    for (int i = 0; i < SIZE; i++)
    {

    }
    //scalenie wartosci 2 podtablic w 1 tablice
    int i = 0;
    int j = 0;
    int begin1 = begin; //aktualny indeks scalanej tablicy
    while (i <= size_left && j <= size_right)
    {
        if (arr1[i] < arr2[j])
        {
            arr[begin1] = arr1[i];

            i++;
        }
        else
        {
            arr[begin1] = arr2[j];
            j++;

        }
        begin1++;
    }
}


template<typename TYPE, int SIZE>
void Array<TYPE, SIZE>::merge_sorting(int begin, int end)
{
    if (begin < end)
    {
        int middle = (begin + end) / 2; // srodek tablicy   
        merge_sorting(begin, middle);
        merge_sorting(middle + 1, end);
        separate_and_merge(begin, middle, end);
    }
}

template<typename TYPE, int SIZE>
void Array<TYPE, SIZE>::DisplayArray()
{
    for (int i = 0; i < SIZE; i++)
    {
        std::cout << arr[i] << std::endl;
    }
}


template<typename TYPE, int SIZE>
void Array<TYPE, SIZE>::getRandomArray()
{
    srand(time(NULL));
    for (int i = 0; i < SIZE; i++)
    {
        arr[i] = std::rand();
    }
}


int main() {

    const int size = 10;

    Array<int, size> tmp;

    tmp.getRandomArray();
    tmp.DisplayArray();
    std::cout << std::endl << std::endl << std::endl << std::endl;
    tmp.merge_sorting(0, size);
    tmp.DisplayArray();

    return 0;
}

Answer 1

我发现的一些问题

int main() {
    ...
    tmp.merge_sorting(0, size);
    ...

    return 0;
}

在上面，您正在将 0, size 传递给 merge_sorting() 方法。 C++ 是从零开始的索引，因此 tmp 数组的最后一个元素的索引是 size-1。你最好tmp.merge_sorting(0, size-1);.

void Array<TYPE, SIZE>::separate_and_merge(int begin, int middle, int end)
{
    ...

    // podpisanie wartosci pod tablice
    for (int i = 0; i < size_left; i++)
    {
        arr1[i] = arr[i];
    }

    ...
}

arr1[i] = arr[i] 应该是 arr1[i] = arr[begin + i]。因为在此函数中，您正在考虑 arr.

的 [begin, end) 部分

    TYPE arr1[size_left]; // inicjacja tablic
    TYPE arr2[size_right];

    while (i <= size_left && j <= size_right)
    {
        if (arr1[i] < arr2[j])
        {
            arr[begin1] = arr1[i];
            i++;
        }
        else
        {
            arr[begin1] = arr2[j];
            j++;

        }
        begin1++;
    }

i <= size_left && j <= size_right 中不应该有 =。以i=size_left为例，由于arr1的大小是size_left，而C++是零索引的，所以会导致index out of range错误。

另外，你考虑过size_left != size_right的情况吗？以size_left > size_right为例。在上面的while循环之后，arr1中还剩下一些元素。所以你需要考虑 arr1 和 arr2.

的剩余元素

    // Copy the remaining elements of arr1[],
    // if there are any
    while (i < size_left) {
        arr[begin1] = arr1[i];
        i++;
        begin1++;
    }

    // Copy the remaining elements of arr2[],
    // if there are any
    while (j < size_right) {
        arr[begin1] = arr2[j];
        j++;
        begin1++;
    }

整个代码为

#include <iostream>

template<typename TYPE, int SIZE>
class Array
{
private:
    TYPE* arr;
public:
    void DisplayArray();
    void separate_and_merge(int begin, int middle, int end);
    void merge_sorting(int begin, int end);
    void getRandomArray();
    Array();
};

template<typename TYPE, int SIZE>
Array<TYPE, SIZE>::Array()
{
    arr = new TYPE[SIZE];
}

template<typename TYPE, int SIZE>
void Array<TYPE, SIZE>::separate_and_merge(int begin, int middle, int end)
{
    int size_left = middle - begin + 1; //rozmair lewej podtablicy
    int size_right = end - middle; // rozmiar prawej podtablicy

    TYPE arr1[size_left]; // inicjacja tablic
    TYPE arr2[size_right];

    // podpisanie wartosci pod tablice
    for (int i = 0; i < size_left; i++)
    {
        arr1[i] = arr[begin + i];
    }

    for (int j = 0; j < size_right; j++)
    {
        arr2[j] = arr[j + middle + 1];
    }

    std::cout << "+++++++[" << begin << ", " << end << ")+++++++++" << std::endl;
    std::cout << "begin: "  << begin  << std::endl;
    std::cout << "middle: " << middle << std::endl;
    std::cout << "end: "  << end    << std::endl;
    std::cout << "size_left: "  << size_left  << std::endl;
    std::cout << "size_right: "  << size_right << std::endl;
    std::cout << "+++++++++++++++++++++" << std::endl;

    std::cout << "======[0, SIZE)==========" << std::endl;
    for (int i = 0; i < SIZE; i++)
    {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    std::cout << "!!!!![begin, end)!!!!" << std::endl;
    for (int i = begin; i < end; i++)
    {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    std::cout << "!!!!!!!!!!!!!!!!!!!!!" << std::endl;

    std::cout << "@@@@@[begin, mid)@@@@" << std::endl;
    for (int i = 0; i < size_left; i++)
    {
        std::cout << arr1[i] << " ";
    }
    std::cout << std::endl;
    std::cout << "@@@@@@@@@@@@@@@@@@@@@" << std::endl;

    std::cout << "$$$$$[mid, end)$$$$" << std::endl;
    for (int i = 0; i < size_right ; i++)
    {
        std::cout << arr2[i] << " ";
    }
    std::cout << std::endl;
    std::cout << "$$$$$$$$$$$$$$$$$$$$$" << std::endl;

    //scalenie wartosci 2 podtablic w 1 tablice
    int i = 0;
    int j = 0;
    int begin1 = begin; //aktualny indeks scalanej tablicy
    while (i < size_left && j < size_right)
    {
        if (arr1[i] < arr2[j])
        {
            arr[begin1] = arr1[i];
            i++;
        }
        else
        {
            arr[begin1] = arr2[j];
            j++;
        }
        begin1++;
    }

    // Copy the remaining elements of
    // arr1[], if there are any
    while (i < size_left) {
        arr[begin1] = arr1[i];
        i++;
        begin1++;
    }

    // Copy the remaining elements of
    // arr2[], if there are any
    while (j < size_right) {
        arr[begin1] = arr2[j];
        j++;
        begin1++;
    }

    std::cout << "======[begin, end)=======" << std::endl;
    for (int i = begin; i < end; i++)
    {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    std::cout << "======[0, SIZE)==========" << std::endl;
    for (int i = 0; i < SIZE; i++)
    {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl << "=========================" << std::endl << std::endl;
}


template<typename TYPE, int SIZE>
void Array<TYPE, SIZE>::merge_sorting(int begin, int end)
{
    if (begin < end)
    {
        int middle = (begin + end) / 2; // srodek tablicy

        merge_sorting(begin, middle);
        merge_sorting(middle + 1, end);

        separate_and_merge(begin, middle, end);
    }
}

template<typename TYPE, int SIZE>
void Array<TYPE, SIZE>::DisplayArray()
{
    for (int i = 0; i < SIZE; i++)
    {
        std::cout << arr[i] << std::endl;
    }
}


template<typename TYPE, int SIZE>
void Array<TYPE, SIZE>::getRandomArray()
{
    srand(time(NULL));
    for (int i = 0; i < SIZE; i++)
    {
        arr[i] = std::rand();
    }
}


int main() {
    const int size = 12;

    Array<int, size> tmp;

    tmp.getRandomArray();
    tmp.DisplayArray();
    std::cout << std::endl << std::endl << std::endl << std::endl;
    tmp.merge_sorting(0, size-1);
    std::cout << std::endl << std::endl;
    tmp.DisplayArray();

    return 0;
}

我正在尝试使用 class 中的数组实现合并排序，但我得到的只是随机值，大部分为零

I'm trying implement mergesort using array in a class, but all i get are random values, mostly zeros

c++

mergesort