c中链表的选择排序

Question

我正在为 C 中的单向链表尝试不同的排序技术。但是，我一直坚持使用指针重排方法进行选择排序。到目前为止，这是我的代码

typedef struct node { 
    int data; 
    struct node *next;
} Node;



   void llselectionsort(Node *head) { 
   Node *marker, *cur = NULL, *min;

   for(marker = head; marker != NULL; marker = marker->next){
         min = marker;
         for(cur = marker->next; cur != NULL; cur = cur->next){
            if(cur->data < min->data) {
               min = cur;
            }
     }
     Node *tmp = marker;
     marker = min;
     tmp->next = marker->next;
     min->next = tmp;

}

我想我使用的指针可能比必要的少了一个，但我仍然不确定。如有任何帮助，我们将不胜感激。

（注意：我知道选择排序被认为是低效的，但是我想了解如何实现它而不管较小的列表排序）

Answer 1

如果使用双指针，这将更容易实现：

NODE * SortList(NODE * pList)
{
NODE **ppNew = &pList;                          /* used to traverse sorted list */
NODE **ppSml;                                   /* ptr to ptr to smallest node */
NODE **ppCur;                                   /* head or previous node */
NODE *pCur;                                     /* current node */
NODE *pTmp;

    if(pList == NULL)                           /* check for NULL list */
        return(pList);
    while((*ppNew)->next != NULL){              /* while not at end list */
        ppSml = ppNew;                          /*   find smallest node */
        ppCur = &((*ppNew)->next);
        while(NULL != (pCur = *ppCur)){
            if(pCur->data < (*ppSml)->data)
                ppSml = ppCur;
            ppCur = &((*ppCur)->next);
        }
/*  for adjacent nodes, 3 pointers are rotated and the order of swaps matters */
        if(*ppNew != *ppSml){                   /* if not the same node */
            pTmp = *ppNew;                      /*     swap node ptrs */
            *ppNew = *ppSml;
            *ppSml = pTmp;
            pTmp = (*ppNew)->next;              /*     swap next ptrs */
            (*ppNew)->next = (*ppSml)->next;
            (*ppSml)->next = pTmp;
        }
        ppNew = &((*ppNew)->next);              /*   advance ppNew */
    }    
    return(pList);
}

Answer 2

您代码的最后四行可以更改为：
int tmp=marker->data;
标记数据=最小->数据；
min->data=tmp;
希望能帮助到你。

c中链表的选择排序

selection sorting of a linked list in c

c

sorting

linked-list

singly-linked-list

selection-sort