鏈接列表合併排序太慢

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