algorithm - 由于链表中没有随机访问，使用快速排序对链表进行排序真的比合并排序慢吗？

Question

来自 http://www.geeksforgeeks.org/merge-sort-for-linked-list/

The slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.

但是，我真的不明白为什么在对链表进行排序时快速排序的性能会比归并排序差。

在快速排序中:

选择一个枢轴需要随机访问，并且需要遍历链表(每次递归 O(n))。

分区可以使用从左到右的扫描方式完成(不需要随机访问):

在合并排序中:

中间拆分需要随机访问，并且需要遍历链表(使用快慢指针机制)(每次递归 O(n))。

合并可以通过从左到右的扫描方式完成(不需要随机访问)。

据我所知，快速排序和合并排序都需要在每次递归中进行随机访问，而且由于链表的非随机访问性质，我不明白为什么快速排序的性能会比合并排序差。

我是不是漏掉了什么？

编辑:我正在查看分区函数，其中 pivot 是最后一个元素，我们按顺序从 lwft 开始扫描。如果分区的工作方式不同(即枢轴位于中间，并且您在每一端维护两个指针)，如果链表是双向链接的，它仍然可以正常工作...

Answer 1

我正在更新此答案以提供更好的比较。在我下面的原始答案中，我包含了一个自底向上合并排序的示例，它使用了一个指向列表的小数组指针。 merge 函数将两个列表合并为一个目标列表。作为替代方案，合并功能可以通过拼接操作将一个列表合并到另一个列表中，这意味着对于伪随机数据，更新链接的时间只有大约一半。对于数组，合并排序比快速排序执行更多的移动但更少的比较，但是如果链表合并是将一个列表合并到另一个列表，则“移动”的数量将减少一半。

对于快速排序，第一个节点可以用作枢轴，只有小于枢轴的节点才会被移动，形成一个在枢轴之前的列表(以相反的顺序)，这也意味着只更新大约一半的链接伪随机数据的时间。

快速排序的问题在于分区并不完美，即使使用伪随机数据也是如此，而归并排序(自上而下或自下而上)相当于完美分区。快速排序的常见分析考虑了通过各种选择枢轴的方式，枢轴落在列表中间 75% 的概率，对于 75%/25% 的拆分(相对于合并排序总是得到 50%/50% 的拆分)。我比较了第一个节点作为枢轴的快速排序与具有 400 万个 64 位伪随机整数的合并排序，快速排序花费了 45% 的时间，增加了 30% 的拼接操作(链接更新或节点“移动”)和其他开销。

---

原始答案

对于链表，有一个自下而上的迭代合并排序版本，它不扫描列表来拆分它们，这避免了随机访问性能慢的问题。链表的自下而上合并排序使用一个小的(25 到 32)节点指针数组。时间复杂度为 O(n log(n))，空间复杂度为 O(1)(指向节点的 25 到 32 指针的数组)。

在那个网页

http://www.geeksforgeeks.org/merge-sort-for-linked-list

我已经发布了一些评论，包括指向链表自下而上合并排序工作示例的链接，但从未收到该组的回复。链接到用于该网站的工作示例:

http://code.geeksforgeeks.org/Mcr1Bf

对于没有随机访问的快速排序，第一个节点可以用作枢轴。将创建三个列表，一个列表用于节点 < pivot，一个列表用于节点 == pivot，一个列表用于节点 > pivot。递归将用于节点 != pivot 的两个列表。这具有 O(n^2) 的最坏情况时间复杂度和 O(n) 的最坏情况堆栈空间复杂度。堆栈空间复杂度可以降低到 O(log(n))，方法是仅在节点 != pivot 的较短列表上使用递归，然后循环返回以使用较长列表的第一个节点作为新的 pivot 对较长列表进行排序.跟踪列表中的最后一个节点(例如使用指向循环列表的尾指针)将允许快速连接其他两个列表。最坏情况下的时间复杂度保持在 O(n^2)。

需要指出的是，如果有空间，将链表移动到数组(或向量)、对数组进行排序并从排序后的数组创建新的排序列表通常要快得多。

示例 C 代码:

#include <stdio.h>
#include <stdlib.h>

typedef struct NODE_{
struct NODE_ * next;
int data;
}NODE;

/* merge two already sorted lists                    */
/* compare uses pSrc2 < pSrc1 to follow the STL rule */
/*   of only using < and not <=                      */
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;
}

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

#define NUMLISTS 32             /* number of lists */
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++)   /* init 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 beyond 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;
}

/* allocate memory for a list */
/* create list of nodes with pseudo-random data */
NODE * CreateList(int count)
{
NODE *pList;
NODE *pNode;
int i;
int r;
    /* allocate nodes */
    pList = (NODE *)malloc(count * sizeof(NODE));
    if(pList == NULL)
        return NULL;
    pNode = pList;                  /* init nodes */
    for(i = 0; i < count; i++){
        r  = (((int)((rand()>>4) & 0xff))<< 0);
        r += (((int)((rand()>>4) & 0xff))<< 8);
        r += (((int)((rand()>>4) & 0xff))<<16);
        r += (((int)((rand()>>4) & 0x7f))<<24);
        pNode->data = r;
        pNode->next = pNode+1;
        pNode++;
    }
    (--pNode)->next = NULL;
    return pList;
}

#define NUMNODES (1024)         /* number of nodes */
int main(void)
{
void *pMem;                     /* ptr to allocated memory */
NODE *pList;                    /* ptr to list */
NODE *pNode;
int data;

    /* allocate memory and create list */
    if(NULL == (pList = CreateList(NUMNODES)))
        return(0);
    pMem = pList;               /* save ptr to mem */
    pList = SortList(pList);    /* sort the list */
    data = pList->data;         /* check the sort */
    while(pList = pList->next){
        if(data > pList->data){
            printf("failed\n");
            break;
        }
        data = pList->data;
    }
    if(pList == NULL)
        printf("passed\n");
    free(pMem);                 /* free memory */
    return(0);
}