频道栏目
首页 > 资讯 > C语言 > 正文

一步一步写算法(之链表排序)

11-11-02        来源:[db:作者]  
收藏   我要投稿

 

【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱: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; 

相关TAG标签
上一篇:一步一步写算法(之字符串查找 上篇)
下一篇:一步一步写算法(之寻路)
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站