0

我正在使用 Qsort，基于employee.lastname.
left是我们跑过多少的计数器。
emptotal, (or right) 是总共有多少。
因为我知道有 5 个，所以我将枢轴点强制为 3。我的问题是，整个事物循环中的第二个递归调用，我无法弄清楚它为什么会循环。它应该向上（或向下）计数，然后遇到它的结束计数器。

#include "./record.h"
#include <string.h>
#include <algorithm>

void externalSort(EmployeeRecord employee[],int empcount,int emptotal)
{
    int left=empcount,
        right=emptotal;    
    EmployeeRecord pivot = employee[3];    
    while (left < right) 
    {
        if (strcmp(employee[left].lastname, pivot.lastname) < 0 )
        {    
            left++; 
        }
        else if (strcmp(employee[right].lastname, pivot.lastname) < 0 )
        {
            right--; 
        }
        else 
        {
            std::swap(employee[left],employee[right]);
            left++;
            right--;
        }
    }

    if (strcmp(employee[left].lastname, pivot.lastname) < 0 )
    {
        std::swap(employee[left],employee[empcount]);
        left--;
    }
    if (strcmp(employee[right].lastname, pivot.lastname) < 0 )
    {
        std::swap(employee[right],employee[empcount]);
        right++;
    }

    if (empcount < right) externalSort(employee,empcount,right);
    if (left < emptotal) externalSort(employee,left,emptotal);
// The 2nd call is what seems to be looping, when I comment it out, 
    //the function doesn't loop.

}
4

2 回答 2

1

employee[3]选择第四件事，而不是第三件事，不管它需要排序多少东西。

循环

while (left < right)

将检查您告诉它检查的项目，但枢轴可能不在该范围内。

在你决定如何处理之后，你还有另外三个错误/事情要考虑。

  1. 你需要在最后一个分支中交换吗？
  2. 当您递归时，请尝试 externalSort(employee,empcount,pivot_index-1)
  3. 与 externalSort(employee,left, emptotal) 类似，您需要使用枢轴索引+1

维基百科上有一些比较清晰的伪代码。您假设每次都可以使用第三点。递归时可能少于 3 个。

于 2013-07-29T17:39:03.567 回答
0

我要做的第一件事是检查以确保您的 strcmp 语句确实在做您认为它们应该做的事情。

if (strcmp(employee[left].lastname, pivot.lastname) < 0 )
{    
left++; 
}
else if (strcmp(employee[right].lastname, pivot.lastname) < 0 )
{
right--; 
}

我相信您的左侧陈述是正确的，但是您正在检查右侧索引处的姓氏是否小于枢轴，而您可能应该检查它是否更大。很多时候，像这样的小事情会给你带来意想不到的代码流。但是，我认为这不会解决所有问题。

于 2013-07-29T17:51:24.687 回答