使用链表进行分区快速排序

Question

我尝试使用链表实现带分区的快速排序。我用常规数组做了几次并且我很好地理解了这个想法，但是对于链表它真的不同。我做了第一部分，然后我卡住了。这是我坚持的要点，假设我有一个数组 { 5, 3, 7, 1, 9, 8, 2, 5, 6 } 所以枢轴总是第一个数字 - 5; 我构建了一个新的 2 数组，一个小于 5（包括 5），另一个大于 5，然后像那样重建主列表 { 3, 1, 2, 5, 5, 7, 9, 8, 6 };

到目前为止我在 3 次运行后得到的最好结果是 1 -> 2 -> 3 -> 5 -> 5 -> 7 -> 9 -> 8 -> 6；但是因为我一直调用 1 作为分区，所以我得到了相同的结果。

我有 2 个函数分区和快速排序 - 快速排序需要递归函数，这是我实现它的主要问题。

标志 == 1 如果数组 (big/small) 不为空

我的代码：

void partition(list **lst, list **pivot, list **small, list **big) {
    list *temp = *lst;
    list *pv = *lst;
    *pivot = pv;
    int big_flag = 0;
    int small_flag = 0;

    *small = (list *)(malloc(sizeof(list)));
    list *n_small = *small;
    list *prev_small = NULL;

    *big = (list *)(malloc(sizeof(list)));
    list *n_big = *big;
    list *prev_big = NULL;

    int p = pv->data;
    pv = pv->next;
    while (pv) {
        if (pv->data <= p) {
            n_small->data = pv->data;
            prev_small = n_small;
            n_small->next = (list *)(malloc(sizeof(list)));
            n_small = n_small->next;
            small_flag = 1;
        } else {
            n_big->data = pv->data;
            prev_big = n_big;
            n_big->next = (list *)(malloc(sizeof(list)));
            n_big = n_big->next;
            big_flag = 1;
        }
        pv = pv->next;
    }
    pv = *lst; // Move the pointer back to the start;

    if (small_flag == 1) {
        n_small = prev_small;
        n_small->next = NULL;
        prev_small = *small;
        // Built the new lst by order 
        while (prev_small) {
            pv->data = prev_small->data;
            pv = pv->next;
            prev_small = prev_small->next;
        }
    }

    // add the pivot to the array 
    pv->data = p;
    pv = pv->next;

    if (big_flag == 1) {
        n_big = prev_big;
        n_big->next = NULL;
        prev_big = *big;
        while (prev_big) {
            pv->data = prev_big->data;
            pv = pv->next;
            prev_big = prev_big->next;
        }
    }
}

这里我真的不确定什么是我的停止条件

void quickSortList(list **lst) {
    list *temp = *lst;
    list *big;
    list *small;
    list *pivot;
    while (temp->next != NULL) {
        partition(lst, &pivot, &small, &big);
        quickSortList(&small);
        quickSortList(&big);
    }
}

Answer 1

数组上的快速排序是这样工作的：

如果数组没有或只有一个元素，则不执行任何操作。否则：
选择一个枢轴并将其移开；
对数组进行分区：小于主元的元素向左移动；
将枢轴放在两个分区之间；这是它在排序数组中的最终位置；
对左右分区进行排序。

这个算法不需要额外的内存。原地运行，所有动作都是元素交换。

链表上的快速排序是这样工作的：

如果数组没有或只有一个元素，则不执行任何操作。否则：
选择一个枢轴并将其移开；
通过将元素移动到两个新列表之一来对数组进行分区，具体取决于元素是否小于主元；
左右分区排序；
连接列表：元素较少 + 主元 + 其他元素

这个算法不需要额外的内存。它工作到位，所有动作都是对头部指针和 next 字段的调整。只有链接发生变化。节点留在它们的位置。

这两个变体之间的主要区别在于您对分区进行排序的时间。数组元素是按位置索引的，所以排序前必须知道分区的位置，所以先放主元。

Linked-list 元素通过以下链接进行索引。在排序之前必须知道头节点和尾节点，所以我们必须先排序。然后我们可以连接列表。

那么让我们来编写我们的函数：

void quicksort(Node **head);

等一下：后面我们需要连接链表，也就是说我们需要找到链表的尾部。这是一个单链表，所以我们必须遍历它。我们可以通过返回排序列表的尾部来节省一些循环，所以：

Node *quicksort(Node **head);

好的，首先是基本案例：

    if (*head == NULL) return NULL;
    if ((*head)->next == NULL) return *head;

我们需要两个列表：

    Node *lt = NULL;        // less than pivot
    Node *ge = NULL;        // greater than or equal to pivot

枢轴是第一个节点，所以*head。 pivot不会被分割，所以我们从之后的节点开始分割：

    Node *node = (*head)->next;

我们遍历链表并删除每个节点。然后我们将该节点插入到两个分区列表之一的头部。（在前面插入更容易也更快，但是这样做会使算法“不稳定”，即不保留两个相等元素的顺序。暂时先不用担心。）

    while (node) {
        Node *next = node->next;

        if (node->data < (*head)->data) {
            node->next = lt;
            lt = node;
        } else {
            node->next = ge;
            ge = node;
        }

        node = next;
    }

我们必须将 next 保存到临时文件中，因为我们正在覆盖刚刚移动的节点的 next 字段。

现在对分区进行排序：

    Node *ltail = quicksort(&lt);
    Node *gtail = quicksort(&ge);

请注意 lt 和 gt（因此 ltail 和 gtail）都可能是 NULL。我们有以下列表 {head, tail}:

{lt, ltail} + {pivot, pivot} + {ge, gtail}

pivot 是 *head。如果ltail不是NULL，ltail->next = pivot和pivot->next = ge，可能是NULL也可能不是。最后，*head一定是整体新头：

    (*head)->next = ge;
    
    if (gtail == NULL) gtail = *head;
  
    if (lt) {
        ltail->next = *head;
        *head = lt;
    }

在这个小舞之后，*head 是新的榜首，gtail 是新的榜尾。

下面是所有内容：

Node *quicksort(Node **head)
{
    // base cases: empty list and single node

    if (*head == NULL) return NULL;
    if ((*head)->next == NULL) return *head;
    
    // partition with *head as pivot

    Node *lt = NULL;        // less than pivot
    Node *ge = NULL;        // greater than or equal to pivot

    Node *node = (*head)->next;

    while (node) {
        Node *next = node->next;

        if (node->data < (*head)->data) {
            node->next = lt;
            lt = node;
        } else {
            node->next = ge;
            ge = node;
        }

        node = next;
    }
    
    // quick-sort recursively

    Node *ltail = quicksort(&lt);
    Node *gtail = quicksort(&ge);

    // rearrange lists: lt -> pivot -> ge

    *head = *head;
    (*head)->next = ge;
    
    if (gtail == NULL) gtail = *head;
  
    if (lt) {
        ltail->next = *head;
        *head = lt;
    }

    return gtail;
}

而here是一个完整的小例子。

最后两点：您可以通过在分区列表的末尾插入来使算法稳定。而且您不需要两个分区列表：您还可以从原始列表中提取较少的节点并将其插入到 le 列表中。 reiaining 元素是另一个分区，如果您正确提取，pivot->next 已经具有正确的值。 Memory-wise 仅使用一个列表不会给您带来任何好处。）

Answer 2

您的实施存在多个问题：

你的 quickSortList() 函数将永远运行因为你没有在循环体中更新 temp 。您应该测试列表是否至少有 3 个元素并且不需要 while 循环。
你没有在递归后重新组合子列表，所以排序无法成功。
分区函数不应分配内存，它应仅将节点分配到 3 个子列表中：一个包含较小数据的节点列表，一个包含数据等于枢轴的节点的列表，一个包含较大数据的节点。但是请注意，第一个和最后一个子列表可能为空。

这是执行稳定排序的完整实现，这对于链表是可行的，但通常不适用于数组，因为它的成本更高。

#include <stdio.h>
#include <stdlib.h>

typedef struct list {
    struct list *next;
    int data;
} list;

void partition(list **lst, list **pivot, list **small, list **big) {
    list *cur = *lst;
    list *pivot_head = cur, **pivot_link = &cur->next;
    list *small_head = NULL, **small_link = &small_head;
    list *big_head = NULL, **big_link = &big_head;
    int data = pivot_head->data;

    /* distribute the list into 3 sublists */
    while ((cur = cur->next) != NULL) {
        if (cur->data == data) {
            *pivot_link = cur;
            pivot_link = &cur->next;
        } else
        if (cur->data < data) {
            *small_link = cur;
            small_link = &cur->next;
        } else {
            *big_link = cur;
            big_link = &cur->next;
        }
    }
    /* close the sublists */
    *pivot_link = NULL;
    *small_link = NULL;
    *big_link = NULL;
    /* return the sublist heads */
    *pivot = pivot_head;
    *small = small_head;
    *big = big_head;
}

list *appendList(list *a, list *b) {
    if (a) {
        list *node = a;
        while (node->next)
            node = node->next;
        node->next = b;
        return a;
    } else {
        return b;
    }
}

void quickSortList(list **lst) {
    list *temp = *lst, *big, *small, *pivot;
    if (temp && temp->next) {
        partition(lst, &pivot, &small, &big);
        quickSortList(&small);
        quickSortList(&big);
        *lst = appendList(small, appendList(pivot, big));
    }
}

list *newList(int data) {
    list *node = malloc(sizeof(*node));
    node->data = data;
    node->next = NULL;
    return node;
}

void freeList(list **lst) {
    list *cur = *lst;
    *lst = NULL;
    while (cur) {
        list *next = cur->next;
        free(cur);
        cur = next;
    }
}

void printList(const list *node) {
    for (; node; node = node->next)
        printf(" %d", node->data);
    printf("\n");
}

int main() {
    list *head = NULL, *tail = NULL, *node;
    int p;

    while (scanf("%d", &p) == 1) {
        node = newList(p);
        if (head == NULL) {
            tail = head = node;
        } else {
            tail = tail->next = node;
        }
    }
    printList(head);
    quickSortList(&head);
    printList(head);
    freeList(&head);
    return 0;
}

我为 quickSortList 和 partition 保留了你的 API，但跟踪所有尾节点以避免在 appendList() 中进行额外扫描会更有效。

如果您可以更改 API，这里有一个无需额外扫描的替代方案：

/* sort the list and return a pointer to the tail node next pointer */
list **quickSortList(list **lst) {
    list *cur = *lst;
    if (cur == NULL) {
        return NULL;
    } else
    if (!cur->next) {
        return &cur->next;
    } else {
        list *pivot = cur, **pivot_link = &cur->next;
        list *small = NULL, **small_link = &small;
        list *big = NULL, **big_link = &big;
        int data = pivot->data;

        /* distribute the list into 3 sublists */
        while ((cur = cur->next) != NULL) {
            if (cur->data == data) {
                *pivot_link = cur;
                pivot_link = &cur->next;
            } else
            if (cur->data < data) {
                *small_link = cur;
                small_link = &cur->next;
            } else {
                *big_link = cur;
                big_link = &cur->next;
            }
        }
        *small_link = NULL;
        if (small) {
            small_link = quickSortList(&small);
            *lst = small;
            *small_link = pivot;
        } else {
            *lst = pivot;
        }
        *big_link = NULL;
        if (big) {
            big_link = quickSortList(&big);
            *pivot_link = big;
            return big_link;
        } else {
            *pivot_link = NULL;
            return pivot_link;
        }
    }
}

使用链表进行分区快速排序

quicksort with partition using linked list

c

partitioning

quicksort