0

我有以下 C++ 代码，我需要使用这些代码来实现合并排序。它部分工作，但由于某种我无法发现的原因而运行无限循环而不进行排序。它还为部分值而不是初始值输出 0.00。（例如输入值 9.12 1.59 输出 1.59 0.00） 但是当我有超过 2 个元素时，它是一个无限循环并且不进行排序。我的作业需要额外的 printf() 才能正确，因此您可以忽略它们进行分析。提前感谢您的帮助！！

double max(double x, double y)
{
   return (x > y) ? x : y;
}

void sort_doubles(vector <double> &v, int print)
{
    int i;
    vector<double> tmp;
    tmp.resize(v.size());

    recursive_sort(v, tmp, 0, v.size(), print);
    printf("%16c",' ');
    for (i = 0; i < v.size(); i++) printf(" %.2lf",v.at(i));
    printf("\n");
}

void recursive_sort(vector<double> &v, vector<double> &temp, int start, int size, int print)
{
    int i,mid,left,right;
    double j;

    if (size == 1) return;

    i = 0;
    mid = start + (size/2);
    left = start;
    right = start + mid;

    printf("B: %5d %5d  ",start, size);
    for (i = 0; i < v.size(); i++) printf(" %.2lf", v.at(i));
    printf("\n");
    recursive_sort(v, temp, left, mid, print);
    recursive_sort(v, temp, left+mid, size-mid, print);

    for(i = 0; i < size; i++)
    {
        /* Check to see if any elements remain in the left array; if so,
         * we check if there are any elements left in the right array; if
         * so, we compare them.  Otherwise, we know that the merge must
         * use take the element from the left array */
        if(left < start + mid && (right == start+size || max(v[left], v[right]) == v[left]))
        {
            temp[i] = v[right];
            right++;
        }
        else
        {
            temp[i] = v[left];
            left++;
        }
    }
    /* Copy the sorted subarray back to the input */
    for(i = start; i < start+size; i++)
    {
        v[i] = temp[i];
    }
    printf("E: %5d %5d  ",start,size,' ');
    for (i = 0; i < v.size(); i++) printf(" %.2lf",v.at(i));
    printf("\n");
}
4

1 回答 1

1

终于想通了！下面是代码，以防有人可能需要它。

double min(double x, double y)
{
    return (x < y) ? x : y;
}

void sort_doubles(vector <double> &v, int print)
{
    int i;
    vector<double> tmp;
    tmp.resize(v.size());

    recursive_sort(v, tmp, 0, v.size(), print);
    printf("%16c",' ');
    for (i = 0; i < v.size(); i++) printf(" %.2lf",v.at(i));
    printf("\n");
}

void recursive_sort(vector<double> &v, vector<double> &temp, int start, int size, int print)
{
    int i,mid,left,right;
    double j;

    if (size == 1) return;

    i = 0;
    mid = size/2;
    left = start;
    right = left+mid;

    printf("B: %5d %5d  ",start, size);
    for (i = 0; i < v.size(); i++) printf(" %.2lf", v.at(i));
    printf("\n");

    recursive_sort(v, temp, left, mid, print);
    recursive_sort(v, temp, left+mid, size-mid, print);

    for(i = 0; i < size; i++)
    {
        /* 
         * Check to see if any elements remain in the left array; if so,
         * we check if there are any elements left in the right array; if
         * so, compare them.  Otherwise, we know that the merge must
         * use take the element from the left array 
         */
        if(left < (start + mid) && (right == start+size || min(v.at(left), v.at(right)) == v.at(left)))
        {
            temp.at(i) = v.at(left);
            left++;
        }
        else
        {
            temp.at(i) = v.at(right);
            right++;
        }
    }

    //Copy the sorted subarray back to the input
    for(i = start; i < start+size; i++)
    {
        v.at(i) = temp.at(i-start);
    }

    printf("E: %5d %5d  ",start,size,' ');
    for (i = 0; i < v.size(); i++) printf(" %.2lf",v.at(i));
    printf("\n");
}
于 2012-10-20T05:56:38.877 回答