c - 单一结构上的QuickSort。不能正常工作

我正在尝试在此结构上用C实现快速排序：

typedef struct ConfigList{
    long **pathid;
    float *sort_coeff;
    int configsize;
    long num_total;
} ConfigList;

我编写的快速排序函数如下所示：

void QuickSort_ConfigList(ConfigList *CL,int num, int start)
{
    if(num>1)
    {
        long *temp_pathid;
        float temp_varscoeff;
        int k;
        float pivot = CL->sort_coeff[num/2];
        int left = start;
        int right = start+num-1;
        while(left<=right)
        {
            if(CL->sort_coeff[left] < pivot)
            {
                left++;
                continue;
            }
            if(CL->sort_coeff[right] > pivot)
            {
                right--;
                continue;
            }
            temp_pathid = CL->pathid[left];
            CL->pathid[left] = CL->pathid[right];
            CL->pathid[right] = temp_pathid;
            temp_varscoeff = CL->sort_coeff[left];
            CL->sort_coeff[left++] = CL->sort_coeff[right];
            CL->sort_coeff[right--] = temp_varscoeff;
        }
        QuickSort_ConfigList(CL,right+1,0);
        QuickSort_ConfigList(CL,num-left,left);
    }
}

我似乎工作不正常，我认为我无法发现一个简单的错误，因为我不知道快速排序很好。下面显示了两个示例输出（注意：这只是将ConfigList->sort_coeff打印到控制台）：
在这里它工作得很好！

    Sort_Coeff = 1.250000
    Sort_Coeff = 1.250000
    Sort_Coeff = 1.277778
    Sort_Coeff = 1.416667
    Sort_Coeff = 1.416667

失败了！

    Sort_Coeff = 0.800000
    Sort_Coeff = 0.861111
    Sort_Coeff = 0.888889
    Sort_Coeff = 0.888889
    Sort_Coeff = 1.083333
    Sort_Coeff = 1.055556
    Sort_Coeff = 1.027778
    Sort_Coeff = 1.138889
    Sort_Coeff = 1.138889
    Sort_Coeff = 0.944444

这似乎是一个我无法发现的小错误，但不幸的是，我还没有找到任何可以在单个结构上操作的实现。

最佳答案

我几乎可以肯定是您对序列长度的处理造成了问题，虽然我还没有花时间对它进行全面的分析，但为了让您能够启动并运行，请考虑以下几点，它消除了“start”点参数，而代之以递归调用的简单序列长度和指针数学：
快速排序并排数组
发送需要相同交换的辅助数组应该是可行的如评论中所述，我认为这正是你要做的：

typedef struct ConfigList
{
    long **pathid;
    float *sort_coeff;
    int configsize;
    long num_total;
} ConfigList;

void QuickSort_ConfigListData(float *coeffs, long** pathids, size_t len)
{
    if (len < 2)
        return;

    float temp_varscoeff;
    long *temp_pathids;

    float pivot = coeffs[len/2];
    size_t left = 0;
    size_t right = len-1;

    while(left<right)
    {
        if (coeffs[left] < pivot)
        {
            ++left;
            continue;
        }

        if (coeffs[right] > pivot)
        {
            --right;
            continue;
        }

        // swap pathids pointers
        temp_pathids = pathids[left];
        pathids[left] = pathids[right];
        pathids[right] = temp_pathids;

        // swap floats
        temp_varscoeff = coeffs[left];
        coeffs[left++] = coeffs[right];
        coeffs[right--] = temp_varscoeff;
    }
    QuickSort_ConfigListData(coeffs, pathids, right);
    QuickSort_ConfigListData(coeffs+left, pathids+left, len - left);
}

void QuickSort_ConfigList(ConfigList* cl)
{
    QuickSort_ConfigListData(cl->sort_coeff, cl->pathid, cl->num_total);
}

用qsort()作弊
尽管内存更为密集（我的意思是大约120万字节，现在这么便宜，我敢肯定我的猫每天早上在垃圾箱里掉的比那还多），你还是可以放弃自己的排序算法，这样做：

// used for sorting with qsort
struct config_s
{
    long *pathid;
    float coeef;
};

// comparator for qsort
int cmp_config_s(const void *arg1, const void* arg2)
{
    struct config_s const* lhs = arg1;
    struct config_s const *rhs = arg2;
    return (lhs->coeff < rhs->coeff) ? -1 : (rhs->coeff < lhs->coeff);
}

void QuickSort_ConfigList(Configlist* cl)
{
    struct config_s *ar = NULL;
    long i=0;

    if (cl->num_total < 2)
        return;

    // build sort-bed
    ar = malloc(cl->num_total * sizeof(*ar));
    for (i=0; i<cl->num_total; ++i)
    {
        ar[i].coeef = cl->sort_coeff[i];
        ar[i].pathid = cl->pathid[i]
    }

    // fire qsort
    qsort(ar, cl->num_total, sizeof(*ar), cmp_config_s);

    // rewrite as sorted
    for (i=0; i<cl->num_total; ++i)
    {
        cl->sort_coeff[i] = ar[i].coeef;
        cl->pathid[i] = ar[i].pathid;
    }
    free(ar);
}

关于c - 单一结构上的QuickSort。不能正常工作，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23692703/