相比較線性表的排序而言，鏈表排序的內(nèi)容稍微麻煩一點(diǎn)。一方面，你要考慮數(shù)據(jù)插入的步驟；另外一方面你也要對(duì)指針有所顧慮。要是有一步的內(nèi)容錯(cuò)了，那么操作系統(tǒng)會(huì)馬上給你彈出一個(gè)exception。就鏈表的特殊性而言，適合于鏈表的排序有哪些呢？

（1）插入排序（適合）

（2）冒泡排序（適合）

（3）希爾排序（適合）

（4）選擇排序（適合）

（5）快速排序（不適合）

（6）合并排序（不適合）

（7）基數(shù)排序（不適合）

（8）堆排序（不適合）

其實(shí)，一般來(lái)說(shuō)。如果涉及到數(shù)據(jù)之間的相對(duì)關(guān)系調(diào)配，那么只適合線性排序；如果只是數(shù)據(jù)內(nèi)容之間的相互交換，那么這種排序方法也比較適合鏈表的排序。快速排序、合并排序、堆排序都涉及到了中間值的選取問(wèn)題，所以不大適合鏈表排序。

為了說(shuō)明鏈表排序是怎么進(jìn)行的，我們可以利用插入排序作為示例，描述鏈表是怎么進(jìn)行插入排序的。

a）首先遍歷節(jié)點(diǎn)，一邊是排序好的節(jié)點(diǎn)，一邊是待排序的節(jié)點(diǎn)

void sort_for_link_node(NODE** ppNode)
{
    NODE* prev;
    NODE* curr;

    if(NULL == ppNode || NULL == *ppNode)
        return;

    curr = (*ppNode) ->next;
    (*ppNode) ->next = NULL;

    while(curr){
        prev = curr;
        curr = curr->next;
        insert_for_sort_operation(ppNode, prev);
    }

    return;
}

b）對(duì)于待插入的節(jié)點(diǎn)，選擇合適的位置插入即可

void insert_for_sort_operation(NODE** ppNode, NODE* pNode)
{
    NODE* prev;
    NODE* cur;

    /* 在第一個(gè)數(shù)據(jù)之前插入pNode */
    if(pNode->data < (*ppNode)->data){
        pNode->next = *ppNode;
        *ppNode = pNode;
        return;
    }

    cur = *ppNode;
    while(cur){
        if(pNode->data < cur->data)
            break;

        prev = cur;
        cur = cur->next;
    }

    pNode->next = prev->next;
    prev->next = pNode;
    return;
}

上一篇：線性結(jié)構(gòu)的處理下一篇：prim算法中

在线观看不卡亚洲电影_亚洲妓女99综合网_91青青青亚洲娱乐在线观看_日韩无码高清综合久久

鏈表排序