【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
相比較線性表的排序而言，鏈表排序的內容稍微麻煩一點。一方面，你要考慮數據插入的步驟；另外一方面你也要對指針有所顧慮。要是有一步的內容錯了，那麼操作系統會馬上給你彈出一個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;
}
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）對於待插入的節點，選擇合適的位置插入即可
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;
}
