cpp - 在不使用 void return 类型（递归）的情况下实现合并排序功能

Question

我打算创建一个递归合并排序函数，returns 一个指向已排序数组的指针。下面是我的程序实现。

代码产生的输出主要由垃圾内存位置组成。由于它是一个递归函数，我在调试它时遇到了麻烦。吓到我的是我是不是对指针、数组以及它们的相互转换理解错了。如果有人可以看一下代码并告诉我我的错误，那将非常有帮助。

在给定指向其第一个元素的指针的情况下打印数组的函数

void printArr(int *arr, int n){
    int *ptr = arr;
    for(int i = 0; i < n; i++){
        cout << *ptr << " ";
        ptr++;
    }
    cout << endl;
}

合并排序函数

这里p是给定数组的指针，n是数组的长度。 l 和 r 分别是数组第一个和最后一个元素的索引。

// returns pointer to the sorted array
int* mergeSort(int *p, int n, int l, int r){
    if(l >= r){
        return &p[l];
    }
    int mid = l + (r-l)/2;
    int *leftArray = mergeSort(p, n, l, mid);
    int *rightArray = mergeSort(p, n, mid+1, r);
    int n1 = mid - l + 1;
    int n2 = r - mid;
    int sortedArray[n1+n2];
    int *ptr = sortedArray; // pointer to the sorted array

    int p1 = 0; // left array index pointer
    int p2 = 0; // right array index pointer
    int idx = 0; // sorted array index pointer
    int flag = 0; /* flag = 1 => all elements of left array have been placed into the sorted array ; flag = 2 => all elements of right array have been placed into the sorted array */

    // putting elements into the sorted array
    for(int i = 0; i < n1+n2; i++){

        if(p1 == n1){
            flag = 1;
            break;
        }
        if(p2 == n2){
            flag = 2;
            break;
        }

        if(*(leftArray+i) > *(rightArray+i)){
            sortedArray[i] = *(leftArray+p1);
            p1++;
            idx++;
        }
        else{
            sortedArray[i] = *(rightArray+p2);
            p2++;
            idx++;
        }
    }

    if(flag == 1){
        // put remaining elements of right array into the sorted array
        for(int i = idx; i < n1+n2; i++){
            sortedArray[i] = *(rightArray+p2);
            p2++;
        }
    }
    if(flag == 2){
        // put remaining elements of left array into the sorted array
        for(int i = idx; i < n1+n2; i++){
            sortedArray[i] = *(leftArray+p1);
            p1++;
        }
    }
    // return the sorted array
    return ptr;
}

主要功能

    int main(){
        int arr[] = {7,2,1,5};
        int n = sizeof(arr)/sizeof(int);
        int *p = arr;
        cout << "Original array: ";
        printArr(arr, n);
        int *f = mergeSort(arr, n, 0, 3);
        cout << "New array: ";
        printArr(f, n);
    }

Answer 1

您的代码已 returned 本地数组的地址，该地址在函数 returned 后无效。然后打印乱码数据：

    int sortedArray[n1+n2];
    int *ptr = sortedArray; // pointer to the sorted array

变成

int *ptr = new int[n1 + n2];
auto sortedArray = ptr;

然后我们得到了一个非垃圾值，但是我们遇到了内存泄漏并且很难处理内存释放，因为在某些边界条件下重新调整的指针可能指向数组 p。

所以return指针不是一个好的设计，它只是浪费了API分配内存和释放内存的调用。最好将函数拆分为两个：第一个分配一个临时缓冲区，第二个处理以缓冲区作为参数的排序并使用递归调用自身。或者就地排序，完全避免临时缓冲区。

cpp - 在不使用 void return 类型（递归）的情况下实现合并排序功能

cpp - Implement a merge sort function without using void return type (recursively)

c++

arrays

algorithm

recursion

mergesort