C 中的快速排序链表

Question

我需要使用Quicksort排序算法对链表的元素进行排序。需要注意的是，我不能只交换键值，还必须交换元素本身。我的代码根本不起作用；我相信我在递归中犯了一个错误。我想要一个解决方案。

我创建了以下函数来实现我的目标：

///ELEMENTO TEM DUAS CHAVES E SEU PRÓXIMO (ENCADEAMENTO SIMPLES)///

struct elemento {
    int chave[2];
    struct elemento *prox;
};

///MOSTRAR A LISTA GERADA///

void mostrar_chaves(struct elemento *lista){

    int i;
    struct elemento *aux;
    aux = lista;
    printf("\n\n\n");

    while(lista){
       printf("%d - ", lista->chave[0]);
       lista = lista->prox;
    }

    printf("\n\n\n");

    while(aux){
       printf("%d - ", aux->chave[1]);
       aux = aux->prox;
    }

}

///QUICK SORT///

struct elemento *particiona(struct elemento *ini, struct elemento *fim){

    struct elemento *pivo, *aux, *t1, *t2, *t3, *teste;
    t1 = ini;
    t2 = ini;
    teste = ini;

    int flag = 0;

    /*printf("\nini = %d\n", ini->chave[0]);
    printf("\nfim = %d\n", fim->chave[0]);*/

    for(pivo = aux = ini; aux && aux != fim; ) {

        if(aux->chave[0] < fim->chave[0]){

            if(ini != aux){
                pivo = aux;
                flag = 1;

                if(t1 == ini){
                    if(t1 != t2){
                        teste = aux;
                        ini = ini->prox;
                        t1->prox = aux->prox;
                        aux->prox = ini;
                        t2->prox = t1;

                        t1 = aux;
                        aux = t2->prox->prox;
                    }
                    else if(t1 == t2){

                        teste = aux;
                        aux = aux->prox;
                        t1 = t1->prox;
                        t1->prox = ini;
                        ini->prox = aux;
                    }
                }

                else{

                    t1->prox = aux; //10 liga no 5
                    aux = aux->prox; //aux 20
                    t1->prox->prox = ini->prox; //5 liga no 40
                    t2->prox = ini; //10 liga no 50
                    ini = ini->prox; //ini 40
                    t2->prox->prox = aux;
                }
            }

            else{
                ini = ini->prox;
            }
        }


        if(flag == 0)
            aux = aux->prox;
        if(t1 != ini && t1->prox != ini){
            t1 = t1->prox;
        }
        if(t2 != aux && t2->prox != aux)
            t2 = t2->prox;

        flag = 0;
    }

    t1->prox = fim; //50 liga no 20
    t3 = fim->prox; //NULL
    t1->prox->prox = ini->prox; //5 liga no 40
    t2->prox = ini; //10 liga no 50
    ini->prox = t3;

    fim = ini;
    ini = aux;

    printf("\npivo = %d\n", pivo->chave[0]);*/
    mostrar_chaves(teste);

    return pivo;
}

void quick_sort(struct elemento *ini, struct elemento *fim){

    struct elemento *pivo;
    printf("\nINI_Q - %d   FIM_Q - %d\n",ini->chave[0], fim->chave[0]);
    if (ini == fim) {
        printf("\nreturn estado anterior\n");
        return;
    }
    pivo = particiona(ini, fim);

    if (pivo && pivo->prox) {
        quick_sort(pivo->prox, fim);
    }

    if (pivo && ini != pivo) {
        quick_sort(ini, pivo);
    }
}

struct elemento *fim(struct elemento *ini){
    struct elemento *fim;

    for(fim = ini; fim && fim->prox; fim = fim->prox);

    return fim;
}

void main(){
setlocale(LC_ALL, "portuguese");

    struct elemento *lista_um, *lista_dois;

    lista_um = NULL;

    lista_um = (struct elemento *) malloc(sizeof(struct elemento)*6);

    lista_dois = lista_um;
    lista_dois->chave[0] = 30;
    lista_dois = lista_dois->prox;
    lista_dois->chave[0] = 50;
    lista_dois = lista_dois->prox;
    lista_dois->chave[0] = 40;
    lista_dois = lista_dois->prox;
    lista_dois->chave[0] = 10;
    lista_dois = lista_dois->prox;
    lista_dois->chave[0] = 5;
    lista_dois = lista_dois->prox;
    lista_dois->chave[0] = 20;

我正在按“chave[0]”对元素进行排序。在代码的最后，输入 6 个元素的顺序为：30, 50, 40, 10, 5, 20，我需要它们的顺序为 5, 10, 20, 30, 40, 50。

Answer 1

对您的代码的一些评论：

• 您假设分区后，第一个节点仍然是左分区中的第一个节点，最后一个节点仍然是右分区中的最后一个节点，但这不能保证。因此，分区完成后，您需要更多信息：哪些是左分区中的第一个和最后一个节点，哪些是右分区中的第一个和最后一个节点。

• 类似的注释适用于

  quick_sort

  ：它接收链表（第一个/最后一个），但调用者在排序完成后将不知道第一个和最后一个节点是什么——回想一下传递了函数参数按值，因此调用者不会知道第一个节点仍然是第一个节点。他们没有其他线索。

我没有试图理解
• t1

  、

  t2

  、

  flag

  、

  teste

  都代表什么——他们的名字不是很能说明问题。

在某些地方，您需要知道链表的第一个和最后一个节点，最好创建一个
• linkedlist

  结构，该结构具有这两个指针（第一个/最后一个）以及操作此类链接的函数列表（向其中添加一个节点、从中提取一个节点、连接两个列表、显示一个列表等）。这将有助于抽象出繁琐的操作并使代码更具可读性。

我会像这样实现快速排序：选择第一个节点的值作为枢轴值（就像你所做的那样），然后访问输入链表中的所有节点并决定是否将它们移动到左列表的末尾，a中间列表或右侧列表。中间列表将包含具有主元值的节点。确保调用者可以访问这三个新的链接列表。由于每个节点都从输入列表
• 移动

  到这三个列表之一，因此输入列表在分区结束时将为空。然后，调用者可以决定如何处理这三个列表：对左列表、右列表应用递归排序，然后连接结果。

以下是我建议的实施方式：

元素（Node）

struct element {
    int key[2];
    struct element *next;
};

struct element *create_element(int key, int payload) {
    struct element *el = malloc(sizeof *el);
    el->key[0] = key;
    el->key[1] = payload;
    el->next = NULL;
    return el;
}

void display_element(struct element *el) {
   printf("%d(%d)", el->key[0], el->key[1]);
}

链表

struct linkedlist {
    struct element *first;
    struct element *last;
};

struct linkedlist *create_linkedlist() {
    struct linkedlist *list = malloc(sizeof(*list));
    list->first = list->last = NULL;
    return list;
}

void linkedlist_append(struct linkedlist *list, struct element *el) {
    if (!list->first) {
        list->first = el;
    } else {
        list->last->next = el;
    }
    list->last = el;
    el->next = NULL;
}

void linkedlist_extend(struct linkedlist *list, struct linkedlist *other) {
    if (!other->first) {
        return; 
    }
    if (!list->first) {
        list->first = other->first;
    } else {
        list->last->next = other->first;
    }
    list->last = other->last;
    other->first = other->last = NULL;
}

struct element *linkedlist_extract_first(struct linkedlist *list) {
    if (!list->first) {
        return NULL;
    }
    struct element* el = list->first;
    list->first = el->next;
    if (!list->first) {
        list->last = NULL;
    }
    el->next = NULL;
    return el;
}

void linkedlist_display(struct linkedlist *list) {
    struct element *el = list->first;
    while (el) {
        display_element(el);
        printf(" -> ");
        el = el->next;
    }
    printf("null");
}

快速排序：

有了上述功能，快速排序的特定代码变得几乎微不足道：

void partition(struct linkedlist *list, struct linkedlist *left,
               struct linkedlist *mid, struct linkedlist *right) {
    // Guaranteed that list is not empty
    struct element *el = linkedlist_extract_first(list); 
    int pivotKey = el->key[0];
    while (el) 
        // Decide where to move this element to:
        struct linkedlist *target = el->key[0] < pivotKey ? left
                                  : el->key[0] > pivotKey ? right
                                  : mid;
        linkedlist_append(target, el); // Move it
        el = linkedlist_extract_first(list); // Take next
    }
}

void quick_sort(struct linkedlist *list) {
    if (list->first == list->last) { // Empty or one element only
        return; // Nothing to do
    }
    struct linkedlist *left = create_linkedlist();
    struct linkedlist *mid = create_linkedlist();
    struct linkedlist *right = create_linkedlist();
    partition(list, left, mid, right); // Will populate left, mid, right
    // At this point list is empty
    quick_sort(left);
    quick_sort(right);
    // Concatenate the sorted partitions
    linkedlist_extend(list, left);
    linkedlist_extend(list, mid);
    linkedlist_extend(list, right);
}

运行示例

int main() {
    struct linkedlist *list = create_linkedlist();
    linkedlist_append(list, create_element(30, 0));
    linkedlist_append(list, create_element(50, 0));
    linkedlist_append(list, create_element(40, 0));
    linkedlist_append(list, create_element(10, 0));
    linkedlist_append(list, create_element( 5, 0));
    linkedlist_append(list, create_element(20, 0));
    printf("Input:\n");
    linkedlist_display(list);
    quick_sort(list);
    printf("Sorted:\n");
    linkedlist_display(list);
    return 0;
}

输出将是：

Input:
30(0) -> 50(0) -> 40(0) -> 10(0) -> 5(0) -> 20(0) -> null
Sorted:
5(0) -> 10(0) -> 20(0) -> 30(0) -> 40(0) -> 50(0) -> null 

最后的评论

快速排序并不是链表的理想候选算法。归并排序是一个更好的选择。

当输入列表已经用不同的值排序时，将第一个节点作为枢轴将导致最坏情况的时间复杂度（因为这样

left

将保持为空，而

right

将只少一个元素）。但是采用另一个枢轴节点将意味着更多的工作，因为您只能从左到右遍历元素 - 没有随机访问。