C 中的快速排序链表

Question

我正在尝试更加熟悉递归，我正在尝试以递归方式而不是迭代方式编写一个函数...我正在尝试为链表创建一个快速排序函数，我一直在重新评估代码，但是我不知道我错过了什么，代码总是把最后一个节点留在列表中，例如...

input list ... 1->2->3->4->NULL
output list .. 4->NULL

这是我的代码...

void lst_qsort(LIST *l){
    if(l==NULL || l->front==NULL || l->front->next==NULL)
        return;
    if(lst_length(l)<=1)
        return;

    LIST *lt = lst_create();
    LIST *pivot = lst_create();

    pivot->front = l->front;
    pivot->back = l->front;

    l->front = l->front->next;
    pivot->front->next = NULL;
    lt = lst_filter_leq(l, pivot->front->val);


    lst_qsort(lt);
    lst_qsort(l);
    lst_concat(l, lt);

}

注释 lst_filter_leq() 是一个函数，它提取所有出现的 x<= 截止点和 returns 提取的所有节点的列表。

LIST * lst_filter_leq(LIST *lst, ElemType cutoff) {
    LIST *lst2 = lst_create();
    NODE *tmp = lst->front;
    int i = 0, n=1;

    while(lst->front != NULL){
        if(lst->front->val <= cutoff){
            lst_push_back(lst2, lst->front->val);
        }
        lst->front = lst->front->next;
    }
    lst->front = tmp;
    for(i=cutoff; i>=0; i--){
        n = lst_remove_all_slow(lst, i);
    }

    return lst2;
}

lst_concat() 将两个列表合并在一起

Answer 1

看看你的代码和你的例子。首先，看起来创建 pivot 列表似乎没有必要，因为您只使用 pivot->front->val，我认为它是列表中的第一个值（因为您之前使用过 pivot->front = l->front）。

因此，对于值 [1, 2, 3, 4]，您在第一步中执行以下操作（我使用伪代码来显示列表成员）：

// you extracted '1' from your list, because you did l->front = l->front->next;
lt = lst_filter_leq([2, 3, 4], 1);

这意味着您什么也没有结束（列表中的 none 个值小于或等于 1）。接下来，您对 l（即 [2, 3, 4]）进行快速排序，然后连接 l 和 lt 的结果。

但是当对 [2, 3, 4] 进行快速排序时，您什么也得不到并且快速排序 [3, 4],
这没什么 [4].
以及 [4] returns [4] 的快速排序。因此你的结果。

看来您忘记了在 l 和 lt 列表之间插入 pivot。

使用 glib 双端队列库的工作实现：

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

// defines to maintain compatibility with OP code
#define LIST GQueue
#define lst_create g_queue_new
#define lst_length g_queue_get_length

// lst_push_back implementation using GQueue
void lst_push_back(LIST *list, int val) {
    g_queue_push_tail(list, GINT_TO_POINTER(val));
}

// lst_pop_front implementation using GQueue
int lst_pop_front(LIST *list) {
    return GPOINTER_TO_INT(g_queue_pop_head(list));
}

// adds elements from list2 to list1
// list2 is destroyed afterwards
void lst_concat(LIST *list1, LIST *list2) {
    int length = lst_length(list2);
    int i, v;
    for (i = 0; i < length; ++i) {
        v = lst_pop_front(list2);
        lst_push_back(list1, v);
    }
    g_queue_free(list2);
}

// filters 'list' elements
// elements less or equal 'value' are returned in newly created list
// elements greater than 'value' are left in 'list'
LIST *lst_filter_leq(LIST *list, int value) {
    LIST *lte = lst_create();
    LIST *gt  = lst_create();
    int length = lst_length(list);
    int i, v;
    for (i = 0; i < length; ++i) {
        v = lst_pop_front(list);
        if (v <= value) {
            lst_push_back(lte, v);
        } else {
            lst_push_back(gt, v);
        }
    }
    lst_concat(list, gt);
    return lte;
}

void lst_qsort(LIST *l) {
    if (l == NULL) {
        return;
    }
    if (lst_length(l) <= 1) {
        return;
    }

    LIST *lt = lst_create();
    LIST *pivot = lst_create();

    int val = lst_pop_front(l);
    lst_push_back(pivot, val);

    // this function divides the list int two parts
    // elements less or equal 'val' are returned in lt list ("right" list)
    // elements greater than 'val 'are left in l list ("left" list)
    lt = lst_filter_leq(l, val);

    lst_qsort(lt); // sort "right" part of list

    lst_qsort(l);  // sort "left" part of list

    lst_concat(l, pivot); // add the pivot element
    lst_concat(l, lt);    // add right part of list
}

void printList(LIST *list) {
    GList *vList = g_queue_peek_head_link(list);
    while (vList != NULL) {
        printf("%d", GPOINTER_TO_INT(vList->data));
        vList = g_list_next(vList);
        if (vList != NULL) {
            printf("->");
        } else {
            printf("\n");
        }
    }
}

int main(void) {
    LIST *l = lst_create();
    lst_push_back(l, 4);
    lst_push_back(l, 3);
    lst_push_back(l, 2);
    lst_push_back(l, 1);

    printf("unsorted: ");
    printList(l);
    lst_qsort(l);
    printf("sorted: ");
    printList(l);

    g_queue_clear(l);

    lst_push_back(l, 1);
    lst_push_back(l, 2);
    lst_push_back(l, 3);
    lst_push_back(l, 4);

    printf("unsorted: ");
    printList(l);
    lst_qsort(l);
    printf("sorted: ");
    printList(l);

    g_queue_clear(l);

    srand(time(NULL));
    int i;
    for (i = 0; i < 16; ++i) {
        lst_push_back(l, rand() % 32);
    }
    printf("unsorted: ");
    printList(l);
    lst_qsort(l);
    printf("sorted: ");
    printList(l);

    g_queue_free(l);

    return 0;
}

示例输出：

unsorted: 4->3->2->1
sorted: 4->3->2->1
unsorted: 1->2->3->4
sorted: 4->3->2->1
unsorted: 27->16->20->4->14->30->26->28->10->13->19->1->30->8->3->14
sorted: 30->30->28->27->26->20->19->16->14->14->13->10->8->4->3->1

C 中的快速排序链表

QuickSorting Linked Lists in C

c

linked-list

quicksort