c - 带有双链表的随机QuickSort

我正在尝试实现随机化的快速排序算法来处理双链表，但我做错了什么。出于某种原因，randomizedQuickSortList()会回忆自己32369次，然后无论在什么地方，我都在randomizedPartitionList()的第一行遇到分段错误（我什至尝试编写一个简单的printf()）。在调试器中运行它，我注意到在某个点之后，p和r（在randomizedPartitionList()中）的值始终分别为1和2。

我确信所有其他功能都可以正常工作，并且我认为randomizedPartitionList()功能也可以完美运行，因为我已经尝试将其与其他算法结合使用

int randomizedPartitionList(node** head, int p, int r){
    int s = rand() % (r-p) + p;
    swapNodes(head, findNode(head, s), findNode(head, r)); //the indices of the findNode() function start from 1
    int x = (*findNode(head, r))->key; //the findNode() function returns a virable of type node**
    int i = p-1;
    int j;
    for(j=p; j<r; j++)
        if((*findNode(head, j))->key <= x){
            i++;
            swapNodes(head, findNode(head, i), findNode(head, j));
        }
    swapNodes(head, findNode(head, i+1), findNode(head, j));
    return (i+1);
}

void randomizedQuickSortList(node** head, int p, int r){
    if(p<r){
        int q = randomizedPartitionList(head, p, r);
        randomizedQuickSortList(head, p, q);
        randomizedQuickSortList(head, q, r);
    }
}

最佳答案

该代码是Lomuto分区方案的变体，应将索引返回到现在已排序的数据透视元素，然后将其排除在递归调用中（否则可能会发生堆栈溢出，这似乎是该问题）：

        randomizedQuickSortList(head, p, q-1);
        randomizedQuickSortList(head, q+1, r);

不包括findnode和swapnodes的代码。我假设findnode通过索引定位一个节点。



可以在分区循环中加快代码的速度，因为i和j都按顺序递增：

int randomizedPartitionList(node** head, int p, int r){
    int s = rand() % (r-p) + p;
    swapNodes(head, findNode(head, s), findNode(head, r)); //the indices of the findNode() function start from 1
    int x = (*findNode(head, r))->key; //the findNode() function returns a variable of type node**
    int i = p-1;
    int j;
    node* inode = *findNode(head, p);
    node* jnode = inode;
    for(j=p; j<r; j++){
        if((jnode->key <= x){
            i++;
            swapNodes(head, inode, jnode);
            inode = nextNode(inode);   // new function
        }
        jnode = nextNode(jnode);       // new function
    }
    swapNodes(head, inode, jnode);
    return (i+1);
}

关于c - 带有双链表的随机QuickSort，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/59201421/