c - C中的合并排序和快速排序

Question

可能重复：
对链接列表进行合并排序

一直在学习 C 和链表，有没有使用链表实现快速排序和合并排序的示例？

Answer 1

链接列表的合并排序 -> http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

快速排序-> http://www.flipcode.com/archives/Quick_Sort_On_Linked_List.shtml

你用谷歌搜索东西吗？使用它......它很好......真的...... :)

Answer 2

合并排序

    #include<stdio.h>
struct node {
int number;
struct node *next;
};

/* add a node to the linked list */
struct node *addnode(int number, struct node *next);
/* preform merge sort on the linked list */
struct node *mergesort(struct node *head);
/* merge the lists.. */
struct node *merge(struct node *head_one, struct node *head_two);

int main(void) {
struct node *head;
struct node *current;
struct node *next;
int test[] = {82, 13, 22, 61, 12, 52, 41, 75, 98, 20};
int i;

head = NULL;
/* insert some numbers into the linked list */
for(i = 0; i < 10; i++)
head = addnode(test[i], head);

/* sort the list */
head = mergesort(head);

/* print the list */
printf(" before after\n"), i = 0;
for(current = head; current != NULL; current = current->next)
printf("%4d\t%4d\n", test[i++], current->number);

/* free the list */
for(current = head; current != NULL; current = next)
next = current->next, free(current);

/* done... */
return 0;
}

/* add a node to the linked list */
struct node *addnode(int number, struct node *next) {
struct node *tnode;

tnode = (struct node*)malloc(sizeof(*tnode));

if(tnode != NULL) {
tnode->number = number;
tnode->next = next;
}

return tnode;
}

/* preform merge sort on the linked list */
struct node *mergesort(struct node *head) {
struct node *head_one;
struct node *head_two;

if((head == NULL) || (head->next == NULL))
return head;

head_one = head;
head_two = head->next;
while((head_two != NULL) && (head_two->next != NULL)) {
head = head->next;
head_two = head->next->next;
}
head_two = head->next;
head->next = NULL;

return merge(mergesort(head_one), mergesort(head_two));
}

/* merge the lists.. */
struct node *merge(struct node *head_one, struct node *head_two) {
struct node *head_three;

if(head_one == NULL)
return head_two;

if(head_two == NULL)
return head_one;

if(head_one->number < head_two->number) {
head_three = head_one;
head_three->next = merge(head_one->next, head_two);
} else {
head_three = head_two;
head_three->next = merge(head_one, head_two->next);
}

return head_three;
} 

快速排序

    #include <iostream.h>
class LinkList{
private:
struct Node 
{
Node* prev;
int value; 
Node *next;
};

Node *first,*t1;
void _display(Node *temp){
if (temp) {
cout<<temp->value<<" , ";
_display(temp->next);
}
}

public :
LinkList(int order){
t1 = new Node();
t1->prev = NULL;
t1->value = order;
t1->next = NULL;
first = t1;
}

~LinkList(){ 
destroy(first);
}

void destroy(Node*current){
Node *temp;
if(current != NULL){
temp = current->next;
delete current;
current = temp;
destroy(current);
}
}


void add(int order){
Node *t2 = new Node();
t2->prev = t1;
t2->value = order;
t2->next = NULL;
t1->next = t2;
t1=t1->next;
}

void operator<<(int order){
add(order);
}

void display(){
_display(first);
}

void sort()
{
Node *current, *cur;

for(current = first; current->next != NULL; current = current->next) {
Node *minimum = current;
for(cur = current ; cur != NULL; cur = cur->next)
{
if(minimum->value > cur->value) 
{
minimum = cur;
}
}
if(minimum != current)
{
Node *current_previous, *current_next, *min_previous, *min_next;

// Initialize them
current_next = current->next;
min_previous = minimum->prev;
min_next = minimum->next;
current_previous = current->prev;

if(current_previous == NULL)
{
// Change the First Node
first = minimum;
}
if(current->next == minimum)
{
// Nodes are Adjacent
minimum->prev = current_previous;
minimum->next = current;

current->prev = minimum;
current->next = min_next;

if(min_next)
{
min_next->prev = current;
}
if(current_previous)
{
current_previous->next = minimum;
}
}
else
{
minimum->prev = current_previous;
minimum->next = current_next;

current->prev = min_previous;
current->next = min_next;

if(current_next)
{
current_next->prev = minimum;
}
if(min_previous)
{
min_previous->next = current;
}
if(min_next)
{
min_next->prev = current;
}
if(current_previous)
{
current_previous->next = minimum;
}
}
current = minimum;
}
}

}
};


void main(){
cout<<"\n\nLinkList =\n";
LinkList *list=new LinkList(4);
*list<<7;
*list<<5;
*list<<3;
*list<<11;
list->display();
list->sort();
cout<<"\n\nSorting\n";
list->display();
delete list;
}