algorithm - 双向链表的分区排序

Question

从 Wirth 的书中翻译成 C 的代码如下

void quicksort(int *array, int left, int right)
{
    int v=array[(left+right)/2];
    int i,j,x;
    i=left;
    j=right;
    do {
        while (array[i]<v) i++;
        while (array[j]>v) j--;
        if (i<=j) {
            x=array[i];
            array[i]=array[j];
            array[j]=x;
            i++;
            j--;
        }
    } while (i<=j);
    if (j>left) quicksort(array, left, j);
    if (i<right) quicksort(array, i, right);
}

但是它使用了数组——我尝试使用双向链表(node structure here):

void partitonSort(node **head,node **tail)
{
    node *v; // here I want to use first or last element as pivot
    node *i,*j;
    do
    {
        while(i->key < v->key) i = i->next;
        while(j->key > v->key) j = j->prev;
        if(/*what boolean expression should I use here*/)
        {
            /*Is it necessary to replace swap operation 
              with insert and delete operations and 
              how to do it */
            i = i->next;
            j = j->prev;
        }
    }
    while(/*what boolean expression should I use here*/);
    if(/*what boolean expression should I use here*/)
           partitonSort(head,&j);
    if(/*what boolean expression should I use here*/)
           partitonSort(&i,tail);      
}

我在代码注释中留下了问题:
- 我应该用插入和删除替换交换操作
以及如何做到这一点
- 我应该使用什么 bool 表达式

Answer 1

这是我的简明解决方案，并附有详细评论:

/* a node of the doubly linked list */
struct Node
{
    int data;
    struct Node *next;
    struct Node *prev;
};

/* A utility function to swap two elements */
void swap ( int* a, int* b )
{   int t = *a;      *a = *b;       *b = t;   }

// A utility function to find last node of linked list
struct Node *lastNode(Node *root)
{
    while (root && root->next)
        root = root->next;
    return root;
}

/* Considers last element as pivot, places the pivot element at its
   correct position in sorted array, and places all smaller (smaller than
   pivot) to left of pivot and all greater elements to right of pivot */
Node* partition(Node *l, Node *h)
{
    // set pivot as h element
    int x  = h->data;

    // similar to i = l-1 for array implementation
    Node *i = l->prev;

    // Similar to "for (int j = l; j <= h- 1; j++)"
    for (Node *j = l; j != h; j = j->next)
    {
        if (j->data <= x)
        {
            // Similar to i++ for array
            i = (i == NULL)? l : i->next;

            swap(&(i->data), &(j->data));
        }
    }
    i = (i == NULL)? l : i->next; // Similar to i++
    swap(&(i->data), &(h->data));
    return i;
}

/* A recursive implementation of quicksort for linked list */
void _quickSort(struct Node* l, struct Node *h)
{
    if (h != NULL && l != h && l != h->next)
    {
        struct Node *p = partition(l, h);
        _quickSort(l, p->prev);
        _quickSort(p->next, h);
    }
}

// The main function to sort a linked list. It mainly calls _quickSort()
void quickSort(struct Node *head)
{
    // Find last node
    struct Node *h = lastNode(head);

    // Call the recursive QuickSort
    _quickSort(head, h);
}