Quick_Sort在单链表 [英] Quick_Sort in Single Linked List
问题描述
我想申请快速排序在一个链接list.I创建的分区功能，它的工作原理是考虑的第一要素为支点：
列表 - ＆GT; 19-＆GT; 8-17-＆GT; 15＆GT; 25-＆GT; 41
（安培;列表）调用分区后，我们得到：
列表 - ＆GT; 16＆GT; 17-＆GT; 8＆GT; 19-＆GT; 25-＆GT; 41
这就是我想要做的：
1），我称之为快速排序（）的列表 - > 19-> 8-17-> 15-> 25-> 41
2）在快速排序，我们呼吁列表中的分区，所以我获得列表 - > 16-> 17-> 8-> 19-> 25-> 41，并在这里'Q'指向主元。
3）现在用q我们分开两部分：list1-> 16-> 17-> 8>空和list2-> 25-> 41，然后调用快速排序对List1中和列表2
4）然后我加入这两个名单与Q。
但我在windows可能是由于程序崩溃来分割fault.Can有人请帮我在这里。
的#include＆LT; stdio.h中＆GT;
＃包括＆LT; stdlib.h中＆GT;
结构节点{
int数据;
结构节点*下一个;
};
typedef结构节点的节点;
无效的显示（节点* P）{
而（P！= NULL）{
的printf（％D，对＆GT;数据）;
p值=对 - ＆gt;接着，
}
的printf（\ N）;
}
节点*创建（INT D）{
节点* P =（节点*）malloc的（的sizeof（节点））;
P-＆GT;数据= D;
对 - ＆gt;接着= NULL;
返回磷;
}
*节点分区（节点**头）{
节点*表= *头;
节点* PV = *头;
INT支点=列表 - ＆GT;的数据;
节点* P =列表 - ＆gt;接着，
节点*温度，* Q =清单;
而（1）{
如果（！P）
打破;
如果（对GT;数据＆LT;透视）{
温度= P;
Q-＆gt;接下来= TEMP-＆gt;接着，
p值=对 - ＆gt;接着，
TEMP-＆gt;接下来=列表;
名单=温度;
}
其他{
Q =磷;
p值=对 - ＆gt;接着，
}
}
*头=清单;
返回PV;
}
节点*快速排序（节点*名单）{
如果（表== NULL ||（名单） - ＆gt;接下来== NULL）
返回列表;
节点* Q，* List1中，* list2中，*温度;
Q =分区（安培;清单）;
List1的=清单;
list2中= Q-＆gt;接着，
TEMP = List1中;
而（1）{
如果（TEMP-＆gt;接着== q）的
{
TEMP-＆gt;接着= NULL;
打破;
}
TEMP = TEMP-＆gt;接着，
}
List1中=快速排序（List1中）;
list2中=快速排序（list2中）;
TEMP = List1中;
而（TEMP-＆GT;！接下来= NULL）
TEMP = TEMP-＆gt;接着，
TEMP-＆gt;接着= Q;
Q-＆gt;接下来= list2中;
返回List1中;
}
诠释的main（）{
节点*的List1 =创建（19），* list2中;
节点* A =创建（8）;
节点* B =创建（17）;
节点* C =创建（16）;
节点* D =创建（25）;
节点* E =创建（41）;
list1-＆gt;接着= A; A-＆gt;接下来= B，B-＆gt;接下来= C; C - ＆gt;接下来= D; D-＆gt;接下来= E;
List1中=快速排序（List1中）;
显示器（List1中）;
}
在这一点上，在一段时间（1）循环：
如果（TEMP-＆gt;接着== Q）
温度可以等于Q（当支点比其余名单小），所以TEMP->下一个永远不会等于q和分割故障发生时，TEMP->接下来== NULL，然后做临时= TEMP->下一步两次。
一个自下而上归并排序会更好，但我猜想这只是一个学习的过程。
更新 - 快速自下而上链表归并排序，使用指针数组到节点，其中，阵列[i]于点尺寸的2到功率我节点的列表（或它的NULL）。节点被同时合并到阵列之一，那么所有节点时合并到阵列，该阵列被合并，以产生一个单一的有序表
的#define NUMLISTS 32 / *列出数* /
typedef结构NODE_ {
结构NODE_ *接下来的;
int数据;
}节点;
NODE * MergeLists（节点*，NODE *）;
NODE * sortlist中（NODE * plist中）
{
NODE * ALIST [NUMLISTS] / *列表的数组* /
NODE * pNode;
NODE * pNext;
INT I;
如果（PLIST == NULL）/ *检查空单* /
返回NULL;
对于（i = 0; I＆LT; NUMLISTS;我++）/ *零数组* /
ALIST [I] = NULL;
pNode = plist中; / *合并节点到ALIST [] * /
而（pNode！= NULL）{
pNext = pNode-＆gt;接着，
pNode-＆gt;接着= NULL;
为（ⅰ= 0;（I＆其中; NUMLISTS）及及（ALIST [I] = NULL）;！我++）{
pNode = MergeLists（ALIST [I]，pNode）;
ALIST [I] = NULL;
}
如果（我== NUMLISTS）
一世 - ;
ALIST [我] = pNode;
pNode = pNext;
}
pNode = NULL; / *合并数组到一个列表* /
对于（i = 0; I＆LT; NUMLISTS;我++）
pNode = MergeLists（ALIST [I]，pNode）;
返回pNode;
}
NODE * MergeLists（NODE * pSrc1，NODE * pSrc2）
{
NODE * pDst = NULL; / *目的地头PTR * /
NODE ** ppDst =安培; pDst; / * PTR，以头或preV-＆gt;下面* /
而（1）{
如果（pSrc1 == NULL）{
* ppDst = pSrc2;
打破;
}
如果（pSrc2 == NULL）{
* ppDst = pSrc1;
打破;
}
如果（pSrc2-＆GT;数据＆LT; pSrc1-＆GT;数据）{/ *如果SRC2＆LT; SRC1 * /
* ppDst = pSrc2;
pSrc2 = *（ppDst =及（pSrc2-＆gt;下面））;
继续;
}其他{/ * SRC1＆LT; = SRC2 * /
* ppDst = pSrc1;
pSrc1 = *（ppDst =及（pSrc1-＆gt;下面））;
继续;
}
}
返回pDst;
}
I am trying to apply quick sort on a single linked list.I have created the partition function which works by considering the first element as pivot:
list->19->8-17->15->25->41
After calling partition(&list) we get :
list->16->17->8->19->25->41
This is what I am trying to do :
1.)I call Quicksort() on list->19->8-17->15->25->41
2.)In QuickSort , We call the partition on list and so I get list->16->17->8->19->25->41 and here 'q' points to the pivot element.
3.)Now using q we split the list in 2 parts : list1->16->17->8->Null and list2->25->41 and then call quicksort on list1 and list 2
4.)Then I join both the lists with 'q'.
But my program crashes in windows probably due to segmentation fault.Can someone please help me out here .
#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node * next;
};
typedef struct node Node;
void display(Node *p){
while(p!=NULL){
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
Node * create(int d){
Node *p=(Node *)malloc(sizeof(Node));
p->data=d;
p->next=NULL;
return p ;
}
Node * partition(Node **head){
Node *list=*head;
Node *pv=*head;
int pivot=list->data;
Node *p=list->next;
Node *temp,*q=list;
while(1){
if(!p)
break;
if(p->data<pivot){
temp=p;
q->next=temp->next;
p=p->next;
temp->next=list;
list=temp;
}
else{
q=p;
p=p->next;
}
}
*head=list;
return pv ;
}
Node * quicksort(Node * list){
if(list==NULL || (list)->next==NULL)
return list;
Node * q,*list1,*list2,* temp;
q=partition(&list);
list1=list;
list2=q->next;
temp=list1;
while(1){
if(temp->next==q)
{
temp->next=NULL;
break;
}
temp=temp->next;
}
list1=quicksort(list1);
list2=quicksort(list2);
temp=list1;
while(temp->next!=NULL)
temp=temp->next;
temp->next=q;
q->next=list2;
return list1;
}
int main(){
Node *list1=create(19),*list2;
Node *a=create(8);
Node *b=create(17);
Node *c=create(16);
Node *d=create(25);
Node *e=create(41);
list1->next=a;a->next=b;b->next=c;c->next=d;d->next=e;
list1=quicksort(list1);
display(list1);
}
At this point in the while(1) loop:
if(temp->next==q)
temp can be equal to q (when pivot is smaller than rest of list), so temp->next will never be equal to q, and the segmentation fault occurs when temp->next == NULL, and then does temp = temp->next twice.
A bottom up merge sort would be better, but I'm assuming this is just a learning exercise.
update - a fast bottom up linked list merge sort that uses an array of pointers to nodes, where array[i] points to a list of size 2 to the power i nodes (or it's NULL). Nodes are merged into the array one at a time, then when all nodes are merged into the array, the array is merged to produce a single sorted list.
#define NUMLISTS 32 /* number of lists */
typedef struct NODE_{
struct NODE_ * next;
int data;
}NODE;
NODE * MergeLists(NODE *, NODE *);
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 aList[] */
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)
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;
}
NODE * MergeLists(NODE *pSrc1, NODE *pSrc2)
{
NODE *pDst = NULL; /* destination head ptr */
NODE **ppDst = &pDst; /* ptr to head or prev->next */
while(1){
if(pSrc1 == NULL){
*ppDst = pSrc2;
break;
}
if(pSrc2 == NULL){
*ppDst = pSrc1;
break;
}
if(pSrc2->data < pSrc1->data){ /* if src2 < src1 */
*ppDst = pSrc2;
pSrc2 = *(ppDst = &(pSrc2->next));
continue;
} else { /* src1 <= src2 */
*ppDst = pSrc1;
pSrc1 = *(ppDst = &(pSrc1->next));
continue;
}
}
return pDst;
}
这篇关于Quick_Sort在单链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
