c - 如何对链表指针进行排序

Question

[50]->[20]->[10]->[30] 请告诉我如何按节点指向的节点按升序或降序对未对齐的列表进行排序。 我认为这就是所谓的链接排序

p.s由于我是C语言和英语的初学者，所以需要考虑。 ptr==tail(ptr不是头)

void sort_data(Node* ptr){
    Node* head = ptr->Next;
    Node* tail = ptr;
    for (int i = 0; i < 10; i++) {
        if (head->Next == tail) {
        }
        if (head->data < head->Next->data) {
            Node* swap1 = head;
            Node* swap2 = head->Next;
            swap1->Next = swap2->Next;
            swap2->Next = swap1;
            tail->Next = swap2;
            tail = tail->Next;
        }
        else {
            head = head->Next;
            tail = tail->Next;
        }
    }
}

Answer 1

该列表是一个循环列表，因此尾指针就足够了，因为如代码所示，tail->next 将产生头指针。该代码不会检查空列表或仅包含单个节点的列表。

冒泡排序通常需要一个循环内的循环(一个外循环和一个内循环)。每个内部循环都会将应该是最后一个的节点移动到列表的末尾。第一个内部循环将最后一个节点放置到位，第二个内部循环将倒数第二个节点放置到位，依此类推，最后一个内部循环将第二个节点放置到位。

为了交换节点，代码需要能够更新前一个节点的下一个指针。例如:

A->B->C->D     // to swap B and C, A's next pointer needs to be updated
A->C->B->D     //  along with B and C's next pointers

由于返回的指针是尾指针，因此可以在第一个内循环之后设置尾指针，因为此时最后一个节点已就位，或者在排序后，可以扫描列表以查找最后一个节点节点。

我建议在排序函数中将循环列表转换为普通列表:

    Node *head = ptr->next;   // same as above
    Node *tail = ptr;         // same as above
    tail->next = NULL;        // convert to normal list

这简化了列表结尾的确定(检查 NULL 与指向特定节点的指针)，因为列表开头或结尾的节点可能在排序过程中交换。

可以通过跟踪列表末尾的已排序节点来优化代码，以避免扫描和比较已排序的节点。

优化冒泡排序的示例代码。设置 pHead 后，列表从循环变为正常(pTail->next = NULL)。 pEnd 用于跟踪未排序列表的末尾并初始化为 NULL。 pnEnd 根据无序检查跟踪未排序列表的末尾，并用于为下一个内部循环设置 pEnd。当 pEnd 是列表中的第二个节点时，排序完成，因为作为单个节点的第一个节点也会被排序。 ppCurr 是指向当前节点的指针，并且是指向 pHead 或某些节点的下一个指针的指针，这简化了处理第一个和后面的节点的逻辑(在不支持指针的其他语言中，一个虚拟节点可以以类似的方式使用，使用类似于 *ppCurr 的 dummy.next)。第一次检查内部循环是否完成，将 pTail 设置为最后一个节点，如果最后两个节点交换，则该节点可能已更改。排序完成后，pTail->next 设置为 pHead，将列表更改回循环列表。

/* bubble sort circular linked list */
NODE * SortList(NODE *pTail)
{
NODE *pHead;                    /* ptr to first node */
NODE *pEnd;                     /* ptr to end of unsorted part of list */
NODE *pnEnd;                    /* pEnd for next pass */
NODE *pNext;                    /* ptr to next node */
NODE **ppCurr;                  /* ptr to ptr to curr node */
    if(pTail == NULL || pTail->next == pTail) /* if empty list or single node */
        return pTail;           /*  return pTail */
    pHead = pTail->next;
    pEnd = pTail->next = NULL;  /* change to normal list */
    do{
        ppCurr = &pHead;        /* set ppCurr to start of list */
        pnEnd = pHead->next;    /* set pnEnd to 2nd node */
        while((pNext = (*ppCurr)->next) != pEnd){
            if((*ppCurr)->data > pNext->data){ /* if out of order swap */
                (*ppCurr)->next = pNext->next;
                pnEnd = pNext->next = *ppCurr;
                *ppCurr = pNext;
            }
            ppCurr = &(*ppCurr)->next; /* advance to next node */
        }
        if(pEnd == NULL)        /* if first time, set pTail */
            pTail = *ppCurr;    /*  in case last two nodes swapped */
        pEnd = pnEnd;           /* update pEnd since rest of list is sorted */
    }while(pEnd != pHead->next); /* loop until pEnd => 2nd node */
    pTail->next = pHead;        /* change to circular list */
    return pTail;
}