在C中使用随机枢轴对链表进行快速排序

Question

我花了很多时间试图为一个类解决这个问题，但我已经无计可施了。我已经找到了很多关于数组和其他选择轴心的方法的资源，但我已经到了极限，在这里真的快疯了，任何帮助都将不胜感激，你无法想象。

#include <stdlib.h>     /*and, malloc*/
#include <stdio.h>      /*printf*/

struct listnode {
    struct listnode *next;
    long value;
};
/*Finds length of list, which is usefull in selecting a random pivot*/
int ListLength (struct listnode *list)
{
    struct listnode *temp = list;
    int i=0;
    while(temp!=NULL)
    {
        i++;
        temp=temp->next;
    }
    return i;
}
/*Prints list*/
void printList(struct listnode *list)
{   
    struct listnode *node;
    node=list;
    printf("nList Valuesn");
    while(node!=NULL)
    {
        printf("%2lo ", node->value);
        node=node->next;
    }
}
/*Creates a list of desired length*/
struct listnode *createList(int lengthOfList)
{
    long i; 
    struct listnode *node, *space;
    space =  (struct listnode *) malloc( lengthOfList*sizeof(struct listnode));
    for( i=0; i< lengthOfList; i++ )
    {  (space + i)->value = 2*((17*i+1)%lengthOfList);
       (space + i)->next = space + (i+1);
    }
    (space+(lengthOfList-1))->next = NULL;
    node = space;
    return node;
}
/*Prof Brass's test*/
void Brass_test(struct listnode *list)
{
    int i;
    printf("nChecking sorted listn");
    for( i=0; i < 100; i++)
    {  
        if( list == NULL )
        { 
            printf("List ended earlyn"); exit(0);
        }
        if( list->value != 2*i )
        {  
            printf("Node contains wrong valuen"); exit(0);
        }
        list = list->next;
   }
   printf("Sort successfuln");
}
/*Selects a random pivot point*/
struct listnode *SelectPivot(struct listnode *list)
{
    int k, n, i = 0;
    n = ListLength(list);

    struct listnode *pivot=list;
    k=rand()%n;
    for (; i < k; ++i)
    {
        pivot=pivot->next;
    }
    return pivot;
}
// Sorts a list using quicksort algo with random pivot point
struct listnode *Quicksort(struct listnode *list)
{
    // Return NULL list
    if (ListLength(list) <= 1) return list;
    struct listnode *less=NULL, *more=NULL, *next, *endl, *temp=list;
    /*Select a random pivot point*/
    struct listnode *pivot = SelectPivot(list);
    printf("Pivot Value = %lon", pivot->value);

    /*Divide & Conquer*/
    while(temp != NULL)
    {
        next = temp->next;
        if(temp->value < pivot->value)
        {
            temp->next = less;
            less = temp;
        }
        else 
        {
            temp->next = more;
            more = temp;
        }
        temp = next;
    }

    less = Quicksort(less);
    more = Quicksort(more);
    // Merge
    if(ListLength(less)!=0)
    {       
        while(endl != NULL)
        {
            endl = less->next;
            less->next = more;
            more = less;
            less = endl;
        }
        return more;        
    }
    else 
    {

        return more;    
    }
}
int main(void)
{
    struct listnode *node;
    node = createList(25);
    printf("Unsorted Listn");
    printList(node);
    printf("nSorted Listn");
    node =  Quicksort(node);

    printf("nList Count node %dn", ListLength(node));
    printList(node);
   /* Brass_test(node);*/


    exit(0);
}

Answer 1

因此，对于那些对代码感兴趣的人来说，以下是问题的解决方案。我只包含了函数self和helper函数。

干杯，

#include <stdlib.h>     //rand, malloc
#include <stdio.h>      //print
#include <time.h>
struct listnode {
    struct listnode *next;
    long value;
};
//Finds length of list, which is usefull in selecting a random pivot
int ListLength (struct listnode *list)
{
    struct listnode *temp = list;
    int i=0;
    while(temp!=NULL)
    {
        i++;
        temp=temp->next;
    }
    return i;
}
// Selects a random pivot point
struct listnode *SelectPivot(struct listnode *list)
{
    int k, n, i = 0;
    n = ListLength(list);
    struct listnode *pivot=list;
    k=rand()%n;  //
    for (; i < k; ++i)
    {
        pivot=pivot->next;
    }
    return pivot;
}
// Sorts a list using quicksort algo with random pivot point
struct listnode *Quicksort(struct listnode *list)
{
    // Return NULL list
    if (ListLength(list) <= 1) return list;
    struct listnode *less=NULL, *more=NULL, *next, *end, *temp=NULL;
    // Select a random pivot point
    struct listnode *pivot = SelectPivot(list);
    // Remove pivot from list
    while(list !=NULL)
    {
        next = list->next;
        if(list->value != pivot->value)
        {
            list->next=temp;
            temp = list;
        }
        list = next;
    }
    // Divide & Conq
    while(temp != NULL)
    {
        next = temp->next;
        if(temp->value < pivot->value)
        {
            temp->next = less;
            less = temp;
        }
        else 
        {
            temp->next = more;
            more = temp;    
        }
        temp = next;
    }
    // Recursive Calls
    less = Quicksort(less);
    more = Quicksort(more);
    // Merge
    if(less != NULL)
    {
        end = less;
        while(end->next != NULL){
            end=end->next;
            }
        pivot->next=more;
        end->next = pivot;
        return less;        
    }
    else{
        pivot->next = more;
        return pivot;   
    }
}

Answer 2

一个问题是合并代码——它反转less列表，同时将其前置到more列表，这会导致垃圾。

Answer 3

在应用快速排序的情况下，最佳实践始终是将FLOOR（n/2）作为枢轴