0

我按照 Wikipedia 上详细介绍的这种递归算法进行合并排序。

这是我想出的代码：

int* merge(int left[], int leftSize, int right[], int rightSize){
int result[leftSize + rightSize];   //The merged array
int resultPointer = 0;  //Index position of where to insert element
int leftPointer = 0;
int rightPointer = 0;

//While length of either of the lists is > 0
while((leftSize > 0) || (rightSize > 0)){

    cout << "Got here" << endl;
    //If length of both left and right lists is > 0
    if((leftSize > 0) && (rightSize > 0)){

        //Compare first elements from both lists and put smallest one in the result list
        if(left[0] < right[0]){
            result[resultPointer] = left[0];
            leftPointer++;
            leftSize--;
        }else if(right[0] < left[0]){
            result[resultPointer] = right[0];
            rightPointer++;
            rightSize--;
        }else{
            //if both elements are the same, put them both in the result list
            result[resultPointer] = left[0];
            leftPointer++;
            leftSize--;
            result[resultPointer++] = right[0];
            rightPointer++;
            rightSize--;
        }
        resultPointer++;    //Increment pointer to point to next empty element

    }else if(leftSize > 0){
        result[resultPointer] = left[0];
        leftPointer++;
        leftSize--;
    }else if(rightSize > 0){
        result[resultPointer] = right[0];
        rightPointer++;
        rightSize--;
    }


}

//int* resultList = result;

return result;
}

int* merge_sort(int list[], int size){

//If list has 1 element then it is sorted so just return that
if(size<=1){
    return list;
}

int middle = size/2;    //Get mid point of given list

//Create left and right arrays
int left[middle];
int right[size-middle];

for(int i = 0; i<size-middle; i++){

    if(i<middle){
        left[i] = list[i];
    }
    right[i] = list[i+middle];
}

//Recursively call merge sort to sort out the sublists
int* leftList = merge_sort(left, middle);
int* rightList = merge_sort(right, size-middle);

//Merge the sorted lists and return a fully sorted list

int* merged = merge(leftList, middle, rightList, size-middle);

return merged;
}

结果输出只是一堆随机数（我认为当某些东西没有被初始化时会发生这种情况）。这个实现可能很愚蠢，但我仍然想知道这里出了什么问题。

干杯

4

3 回答 3

2

您正在从指向局部变量的合并函数返回一个指针。当您从合并函数返回时，局部变量将超出范围。因此，您返回一个未指向任何有效内存的指针。

于 2012-08-18T15:04:44.490 回答
0

您的合并函数正在返回一个指向局部变量的指针。

于 2012-08-18T15:04:28.640 回答
0

您遇到的不仅仅是简单的初始化问题：
编译时出现以下错误：

> g++ -Wall -Wextra -pedantic merge.cpp  

merge.cpp: In function ‘int* merge(int*, int, int*, int)’:   
merge.cpp: 2: error: ISO C++ forbids variable-size array ‘result’  
merge.cpp:10: error: ‘cout’ was not declared in this scope  
merge.cpp:10: error: ‘endl’ was not declared in this scope  
merge.cpp: 2: warning: address of local variable ‘result’ returned  

merge.cpp: In function ‘int* merge_sort(int*, int)’:  
merge.cpp:62: error: ISO C++ forbids variable-size array ‘left’  
merge.cpp:63: error: ISO C++ forbids variable-size array ‘right’

其中我会说：

merge.cpp: 2: warning: address of local variable ‘result’ returned

那个很关键。但你应该修复所有这些。

于 2012-08-18T15:49:52.897 回答