从链表创建数组并对数组进行排序C

Question

有人告诉我，对链表进行排序的最佳方法是将该链表复制到数组中并对该数组进行排序。

#define SIZE 7000 

所以我的链接列表：

typedef struct no{ 

    char *nome; 
    int count; 
    struct no * prox; 
}*link; 

我的数组：

typedef struct MyArray 
{ 
    char name[141]; 
    int count; 
}MyArray; 

MeuArray v[SIZE]; 

现在我创建阵列功能：

void create_array() 
{ 
link tmp = head; 
int cont = 0; 
int i; 

while (tmp != NULL) 
    { 
     strcpy(v[cont].nome, tmp->nome); 
     v[cont].count = tmp->count; 
     tmp = tmp->prox; 
     cont++; 
    } 
for (i = 0; i < SIZE; i++) 
    printf("%s %d\n", v[i].nome, v[i].count); 
} 

不知道这是正确的。 现在我不知道哪个是最好的/最快的。 qsort或其他。 如果快速排序：

int compare(struct MeuArray *elem1, struct MeuArray *elem2) 
{ 
if (elem1->count < elem2->count) 
    return -1; 

else if (elem1->count > elem2->count) 
    return 1; 

else 
{ 
    if (strcmp(elem1->name, elem2->name) > 1) 
     return 1; 
    else 
     return -1; 
} 
} 

我也试过这种方式（排序我的链接列表）：

void insertionSort(link current) 
{ 
link head = current; 
link inserP = head; 
current = current->prox; 
while (current != NULL) 
{ 
    inserP = head; 

    while (inserP != current) 
    { 
     if (inserP->count > current->count) 
     { 
      int temp = current->count; 
      current->count = inserP->count; 
      inserP->count = temp; 
     } 
     else /* if (inserP->count < current->count) */ 
      inserP = inserP->prox; 

     /*else 
      { 
       if (strcmp(inserP->name, current->name) > 0) 
       { 
        char temp2 = strcpy(temp2, current->name); 
        strcpy(current->name, inserP->name); 
        strcpy(inserP->name, temp2); 
       } 
       else 
        inserP = inserP->prox; 
      } */ 
     } 
    } 
    current = current->prox; 
} 

有：

link head = NULL; 

apreciated任何帮助。

编辑

我的qsort我希望被计数则首先比较的名字。 问题是我只能按数量排序。 如何按名称排序？

代码：

int compare (const void * a, const void * b) 
{ 

MeuArray *MeuArrayA = (MeuArray *)a; 
MeuArray *MeuArrayB = (MeuArray *)b; 

if (MeuArrayB->count > MeuArrayA->count) 
    return 1; 
else if (MeuArrayB->count < MeuArrayA->count) 
    return -1; 
else 
{ 
    if (strcmp(MeuArrayB->nome, MeuArrayA->nome)) 
     return 1; 
    else 
     return -1; 
} 
} 

Answer 1

如果你想不必使用数组的选项，但仍希望有一个快速排序，这里是一个自下而上的合并排序的链表的例子，使用小（26到32）指向节点的指针数组。这通常是最快的算法，并且通常如何实现C++ std :: list :: sort（）。在我的系统（英特尔2600K，3.4 GHz）上，它可以在不到一秒的时间内对400万个节点的链表进行排序。

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

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

Answer 2

如果你想排序链接列表，那么你不需要将其转换为数组。你能做到这一点的链接列表，有效的方式

while(t1!=NULL) 
{ 
    count++; 
    t1=t1->ptr; 
} 
for(i=0;i<count;i++) 
    { 
    t1=START; 
    for(j=0;j<count-i-1;j++) 
    { 
     if(t1->info>(t1->ptr)->info) 
     { 
int temp=t1->info; 
t1->info=(t1->ptr)->info; 
(t1->ptr)->info=temp; 
     } 
     t1=t1->ptr; 
    } 
    } 

其使用冒泡排序 更多信息click here