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))。

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

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

我在这里遗漏了什么吗？

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

Answer 1

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

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

快速排序的问题在于，即使使用伪随机数据，分区也不完美，而合并排序(自上而下或自下而上)具有相当于完美分区的效果。快速排序的常见分析考虑通过选择主元的各种方式，主元落在列表中间 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

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