返回首页 一步一步写算法

链表排序

相比较线性表的排序而言,链表排序的内容稍微麻烦一点。一方面,你要考虑数据插入的步骤;另外一方面你也要对指针有所顾虑。要是有一步的内容错了,那么操作系统会马上给你弹出一个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;
}  
上一篇: 哈希二叉树 下一篇: 字符串查找 上篇