尝试对结构数组进行快速排序时遇到问题

Question

我必须读取 .txt 文件并将单词和它们写入文件的时间保存在结构数组中。我试图在互联网上寻找一种方法来做到这一点，但一切都是关于 C++ 的。

其他一切似乎都正常。单词存入数组没问题，就是排序不行

结构：

typedef struct
{
    char palavra[50]; // the word
    int ocorrencia; // times it's written
} dicionario;

我对快速排序的尝试：

void quickSort(dicionario tabela[], int inicio, int tamanho)
{
    
    int i = inicio, j = tamanho;
    int temp;
    int pivot = tabela[(i + j) / 2].ocorrencia;

    while(i<=j)
    {
        while(tabela[i].ocorrencia < pivot) i++;
        while(tabela[j].ocorrencia > pivot) j--;
        if(i<=j)
        {
            temp = tabela[i].ocorrencia;
            tabela[i].ocorrencia = tabela[j].ocorrencia;
            tabela[j].ocorrencia = temp;
            i++;
            j++;
        }
    }

    if(inicio < j) quickSort(tabela,inicio,j);
    if(i < tamanho) quickSort(tabela,i,tamanho);

}

当我运行代码时，它只是结束而不返回任何东西，即使我试图在最后打印它。

Answer 1

wandbox 示例对指向字符串的指针数组进行排序。您想要对结构数组进行排序，例如dicionario a[20]; 在 .ocorrencia 字段上。你叫

qsort(a, 20, sizeof(dicionario), cmpdicionario);。然后使用：

int cmpdicionario(const void *a, const void *b)
{
    // a and b are really pointers to structs.
    int ai = ((dicionario *)a)->ocorrencia;
    int bi = ((dicionario *)b)->ocorrencia;
    return (ai < bi) ? -1 : (ai > bi) ? 1 : 0;
}

将比较函数放在调用 qsort() 之前以保持简单。

如果您没有足够高的计数来担心溢出，您可以 return ai - bi; 但我推荐上面的方法。

我没怎么研究你的快速排序。做对是一件棘手的事情。如果您需要自己编写代码，则应密切关注已知的好示例。我会注意到你的 j++ 应该是 j--，你的交换应该交换整个结构，而不仅仅是一个字段，因为你想保持单词与其计数相关联。可能还有其他BUG。

此外，如果您需要编写自己的排序代码，并且不需要高性能，请使用 Shell 排序。它更短，更容易正确。通常大约是快速排序速度的 1/5 到 1/2，通常足够快。如果它可能少于 50 个元素并且您不需要经常运行它，插入排序就可以甚至更简单。另外，插入排序是“稳定的”，也就是说，它将保持具有相同计数的元素的原始顺序。在这里可能不相关，但有时很有用。

尝试对结构数组进行快速排序时遇到问题

Trouble trying to quickSort an array of structs

c

sorting

struct

quicksort