C++算法之鏈表排序

相比較線性表的排序而言，鏈表排序的內容稍微麻煩一點。一方面，你要考慮數據插入的步驟；另外一方面你也要對指針有所顧慮。要是有一步的內容錯了，那么操作系統會馬上給你彈出一個exception。就鏈表的特殊性而言，適合于鏈表的排序有哪些呢？
（1）插入排序 （適合）
（2）冒泡排序 （適合）
（3）希爾排序 （適合）
（4）選擇排序 （適合）
（5）快速排序 （不適合）
（6）合并排序 （不適合）
（7）基數排序 （不適合）
（8）堆排序 （不適合）
其實，一般來說。如果涉及到數據之間的相對關系調配，那么只適合線性排序；如果只是數據內容之間的相互交換，那么這種排序方法也比較適合鏈表的排序。快速排序、合并排序、堆排序都涉及到了中間值的選取問題，所以不大適合鏈表排序。
為了說明鏈表排序是怎么進行的，我們可以利用插入排序作為示例，描述鏈表是怎么進行插入排序的。     a）首先遍歷節點，一邊是排序好的節點，一邊是待排序的節點

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;  

}
</pre>     b）對于待插入的節點，選擇合適的位置插入即可
void insert_for_sort_operation(NODE* ppNode, NODE pNode)

{

    NODE prev;

    NODE cur;


/* 在第一個數據之前插入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;  

}

</pre>