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;  
}  

    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;  
}  

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。