0

我正在尝试用 C 编写代码以在合并函数中mergesort使用循环。for不幸的是，它不起作用。在函数中，我按降序main创建一个arrayon 10 ，然后调用该函数对它们进行排序。合并函数显然存在错误，因为从未实现升序，并且在某些数组大小中会出现一些长数字。我究竟做错了什么？这是功能：intsmergesort

#include <stdio.h>
#include <stdlib.h>


void mergesort(int array[], int left, int right);

int main()
{
    int i;
    int arr[10];
    for(i=10;i>0;i--){
        arr[10-i]=i;
    }
    for(i=0;i<10;i++){
        printf("arr[%d] = %d\n",i,arr[i]);
        }
    mergesort(arr,0,9);
    puts("\n");
    for(i=0;i<10;i++){
        printf("arr[%d] = %d\n",i,arr[i]);
        }
    return 0;
}

void mergesort(int array[], int left, int right)
{
    void merge(int array[],int left, int mid, int right);
    int mid;
    if(left<right){
        mid=(left+right)/2;
        mergesort(array,left,mid);
        mergesort(array,mid+1,right);
        merge(array,left,mid,right);
    }
}

void merge(int array[], int left, int mid, int right)
{
    int i;
    int l=0;
    int r=mid+1;
    int arr_sorted[10];

    for(i=0;i<=right;i++){
        if((l<=mid) && (r<=right)){
            if(array[l]<array[r]){
                arr_sorted[i]=array[l];
                l++;
            }
            else {
                arr_sorted[i]=array[r];
                r++;
            }
        }
        if(l>mid){
            arr_sorted[i]=array[r];
            r++;
        }
        if(r>right){
            arr_sorted[i]=array[l];
            l++;
        }
    }
    for(i=0;i<=right;i++){
        array[i]=arr_sorted[i];
    }
}
4

3 回答 3

5

首先看起来很奇怪的是为什么您将left参数传递给merge，但从0to迭代right；left甚至没有在这个函数中使用。

于 2012-12-30T09:36:31.957 回答
3

合并功能中需要的一些更正：

void merge(int array[], int left, int mid, int right)
{
    int i;
    int l=left; //If you are passing left, then it should be used here !!
    int r=mid+1;
    int arr_sorted[10];

    for(i=0;(l<=mid)&&(r<=right);i++){ 
//Your condition for this loop unnecessarily complicates the rest of the code. This is a better way to go about it
//The loop body is fine
       if(array[l]<array[r]){
                arr_sorted[i]=array[l];
                l++;
            }
            else {
                arr_sorted[i]=array[r];
                r++;
            }
        }

//Now, checking for remaining elements and adding them to the result
//The conditions are simple because of the test condition we used in the previous for loop
        if(l>mid){
           for(;r<=right;r++,i++) arr_sorted[i]=array[r];
        }
        if(r>right){
            for(;l<=mid;l++,i++)  arr_sorted[i]=array[l];
        }
    }
    for(i=0;i<=right;i++){
        array[i]=arr_sorted[i];
    }
}

此外，作为一种风格，尽量将前向声明保留在一个地方（更重要的是函数是相关的）。代替 ：

void mergesort(int array[], int left, int right)
{
    void merge(int array[],int left, int mid, int right);//This line should be moved to the top with the mergesort forward declaration
    int mid;
    if(left<right){
        mid=(left+right)/2;

尝试做：

#include <stdio.h>
#include <stdlib.h>


void mergesort(int array[], int left, int right);
void merge(int array[],int left, int mid, int right); // <--------

不过，这只是一个偏好问题。

于 2012-12-30T09:43:03.723 回答
1

这是整个工作合并排序，您可以看到差异，如果您有任何其他问题，请告诉我。我不得不更改名称，因为 stdlib 具有合并排序实现。

#include <stdio.h>
#include <stdlib.h>


int mymergesort(int array[], int left, int right);

int main()
{
    int i;
    int arr[10];
    for(i=10;i>0;i--){
        arr[10-i]=i;
    }
    for(i=0;i<10;i++){
        printf("arr[%d] = %d\n",i,arr[i]);
        }

    mymergesort(arr,0,9);
    puts("\n");
    for(i=0;i<10;i++){
        printf("arr[%d] = %d\n",i,arr[i]);
        }
    return 0;
}

int mymergesort(int array[], int left, int right)
{
    void mymerge(int array[],int left, int mid, int right);
    int mid;

    mid=(left+right)/2;
    if(left<right){
        mymergesort(array,left,mid);
        mymergesort(array,mid+1,right);
        mymerge(array,left,mid,right);
    }
    return 0;
}

void mymerge(int array[], int left, int mid, int right)
{
    int i=0;
    int l=left;
    int r=mid+1;
    int arr_sorted[10];

    for(i=left;i<=right;){
        if((l<=mid) && (r<=right)){
            if(array[l]<array[r]){
                arr_sorted[i]=array[l];
                l++;
                i++;

            }
            else {
                arr_sorted[i]=array[r];
                r++;
                i++;
            }
        }

        if(l>mid){
            for(;r<=right;r++){   
                arr_sorted[i]=array[r];
                i++;

            }   
            break;
        }
        if(r>right){
            for(;l<=mid;l++){

                 arr_sorted[i]=array[l];
                    i++; 
            }
            break;
        }
    }
    for(i=left;i<=right;i++){
        array[i]=arr_sorted[i];
    }
}
于 2012-12-30T11:59:59.873 回答