雙鏈錶快速排序在C

Question

任何人都可以幫助我在這裏，因爲我不知道爲什麼我的排序功能是排除除了頭之外的所有列表？下面是輸出：

正向方式：208 1 87 116 149 238 284 304 327 410 426 523 552 583 625 695 803 848 853 944
反向方式：944 853 848 803 695 625 583 552 523 426 410 327 304 284 238 149 116 87 1 208

正如你所看到的，它只是在208之後插入，它保留了208，即使它對所有列表進行排序。下面是實際的列表之前排序：

前進的道路：208 523 284 410 304 426 583 848 552 803 87 238 1 695 853 149 625 944 327 116
反向方式：116 327 944 625 149 853 695 1 238 87 803 552 848 583 426 304 410 284 523 208

這裏是我的代碼：

void list_ins_aft (node_t *old ,node_t *new) 
{ 

    if (old->next != NULL) 
    { 
    old->next->prev = new; 
    } 
    new->next = old->next; 
    new->prev = old ; 

    old->next = new ; 
} 

void list_detach(node_t *n , dlist_t *nlst) 
{ 

    if (n->prev == NULL) 
    { 
    nlst->head = n->next; 
    } 
    else 
    { 
    n->prev->next = n->next; 
    } 

    if(n->next == NULL) 
    { 
    nlst->tail = n->prev; 
    } 
    else 
    { 
    n->next->prev = n->prev; 
    } 
} 


void qsort_segment (node_t *t1 , node_t *t2 , dlist_t *lst) 
{ 

    /* skip 0 or 1 lengh segment */ 
    if (t1 == t2 || t1->next == t2) 
    return; 
    /*define pivot and make sure its the first element 
    * so put the less before pivot and bigger after pivot 
    * */ 
    node_t *piv; 
    piv = t1->next; 
    node_t *s,*b,*temp = piv , *x = t2 ? t2->next : NULL ; 

    for (s = piv->next ; s != x ; s = b) 
    { 

    b = s->next ; 

    list_detach (s ,lst) ; 

    if (s->value < piv->value) 
    { 
     list_ins_aft(t1 , s); 
    } 
    else 
    { 
     list_ins_aft (piv , temp == piv ? (temp = s) : s); 
    } 
    } 

    /* now sort new segments on right and left sides of pivot the same way */ 
    qsort_segment (piv , temp ,lst); 
    qsort_segment (t1 , piv->prev , lst); 

} 

Answer 1

你可能一開始稱其爲qsort_segment(list.head, list.tail, &list);其中list是你dlist_t包含head和tail指向第一個和第二個指針。列表中的最後一個元素。

/*define pivot and make sure its the first element 
* so put the less before pivot and bigger after pivot 
* */ 
node_t *piv; 
piv = t1->next; 

這不會做它的評論說，這臺透視到列表中的第二個元素。考慮到遞歸調用，意圖似乎是t1指向要排序的部分之前的元素，而t2指向該部分中的最後一個元素。但是在列表的前面，第一個之前沒有元素。所以

if (s->value < piv->value) 
    { 
     list_ins_aft(t1 , s); 
    } 

確保列表中的第一個節點在整個排序中保持不變。

您需要某種方式在列表的前面插入一個元素，例如list_ins_bef功能模擬list_ins_aft或顯式list_ins_front(node_t *new, dlist_t *lst)。