c - 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<=截止点并返回所有提取节点的列表。

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);

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

但是当快速排序 [2, 3, 4] 时，你什么也得不到，而快速排序 [3, 4]，
这没什么，[4]。
[4] 的快速排序返回 [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