c++ - 循环递归函数c++

Question

我正在使用基于 employee.lastname 的 Qsort。
left 是我们已经运行了多少个计数器。
emptotal，(或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.

}

Answer 1

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

循环

while (left < right)

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

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

1. 是否需要在最后一个分支中交换？
2. 递归时，尝试 externalSort(employee,empcount,pivot_index-1)
3. 类似于 externalSort(employee,left, emptotal) 你需要使用 pivot index+1

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