c - 链表的合并排序太慢

Question

我的任务是读取文件并对其进行排序，全部使用单向链表。我实现了合并排序，但测试系统说它在处理大文件时速度太慢。我该如何优化它？

void merge_sort(list *a, list *tmp, int n) {
    int k, i, rcount;
    list *cursor, *l, *r, *end;
    k = n/2;
    if(n == 1) {
        return;
    }
    l = a;
    end = list_get(a, k);
    r = end;
    merge_sort(a, tmp, k);
    merge_sort(r, tmp, n - k);
    rcount = k;
    for(cursor = tmp, i = 0; i < n; cursor = cursor->next, i++) {
        if((l != end) && (((rcount == n) || (strcmp(l->value, r->value) < 0)))) {
            cursor->value = l->value;
            l = l->next;
        } else {
            cursor->value = r->value;
            r = r->next;
            rcount++;
        }
    }
    for(cursor = tmp, i = 0; i < n; cursor = cursor->next, a = a -> next, i++) {
        a->value = cursor->value;
    }
    return;
}

Answer 1

我假设要求是对列表进行排序，而不是对节点内的数据进行排序(这可以通过创建指向节点的指针数组并通过指针数组使用合并/快速排序来重新排列来完成节点内的数据)。

使用自上而下的合并/快速排序对于链表来说不是一个好的方法，因为所有扫描都是为了模拟随机访问迭代器以递归地拆分列表。

自下而上的方法要快得多。您可以使用 4 个指向节点的指针作为指向 4 个列表的指针，并实现类似磁带排序的功能，但这需要使用计数器来跟踪每个列表中运行的逻辑结束。维基文章:

http://en.wikipedia.org/wiki/Merge_sort#Use_with_tape_drives

使用一个小的(26 到 32 个)指针数组更简单、更快速。这是 HP/Microsoft 标准模板库中用于对列表进行排序的算法。维基文章:

http://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

示例代码。在我的系统上，Intel 2600K 3.4ghz，它可以在大约一秒钟内将 400 万个节点以伪随机 32 位无符号整数作为数据进行排序。

/* prototype */
NODE * MergeLists(NODE *pSrc1, NODE *pSrc2);

/* sort list using array of pointers to first nodes of list   */
/* aList[i] = NULL or ptr to list with 2 to the power i nodes */

#define NUMLISTS 32                 /* size of array */
NODE * SortList(NODE *pList)
{
NODE * aList[NUMLISTS];             /* array of lists */
NODE * pNode;
NODE * pNext;
int i;
    if(pList == NULL)               /* check for empty list */
        return NULL;
    for(i = 0; i < NUMLISTS; i++)   /* zero array */
        aList[i] = NULL;
    pNode = pList;                  /* merge nodes into array */
    while(pNode != NULL){
        pNext = pNode->next;
        pNode->next = NULL;
        for(i = 0; (i < NUMLISTS) && (aList[i] != NULL); i++){
            pNode = MergeLists(aList[i], pNode);
            aList[i] = NULL;
        }
        if(i == NUMLISTS)           /* don't go past end of array */
            i--;
        aList[i] = pNode;
        pNode = pNext;
    }
    pNode = NULL;                   /* merge array into one list */
    for(i = 0; i < NUMLISTS; i++)
        pNode = MergeLists(aList[i], pNode);
    return pNode;
}

/* mergelists -  compare uses src2 < src1           */
/* instead of src1 <= src2 to be similar to C++ STL */

NODE * MergeLists(NODE *pSrc1, NODE *pSrc2)
{
NODE *pDst = NULL;                  /* destination head ptr */
NODE **ppDst = &pDst;               /* ptr to head or prev->next */
    if(pSrc1 == NULL)
        return pSrc2;
    if(pSrc2 == NULL)
        return pSrc1;
    while(1){
        if(pSrc2->data < pSrc1->data){  /* if src2 < src1 */
            *ppDst = pSrc2;
            pSrc2 = *(ppDst = &(pSrc2->next));
            if(pSrc2 == NULL){
                *ppDst = pSrc1;
                break;
            }
        } else {                        /* src1 <= src2 */
            *ppDst = pSrc1;
            pSrc1 = *(ppDst = &(pSrc1->next));
            if(pSrc1 == NULL){
                *ppDst = pSrc2;
                break;
            }
        }
    }
    return pDst;
}