鍊式結構的歸并排序

#include <iostream>

using namespace std;

struct elem

{

elem()

{

value = 0;

next = NULL;

}

int value;

elem * next;

};

struct node

{

node()

{

head = tail = NULL;

}

elem* head;

elem* tail;

};

int compare_node(elem* elem_1, elem* elem_2)

{

if(elem_1->value < elem_2->value)

{

return -1;

}

else if(elem_1->value == elem_2->value)

{

return 0;

}

else

{

return 1;

}

}

/*

對鍊式結構進行歸并排序, 輸入是待排序連結清單表頭，傳回值是排序後的表頭指針

sort_type = -1: 升序， 1:降序

*/

elem* sort_list(elem *phead, int sort_type)

{

elem* head_1 = NULL;

elem* head_2 = NULL;

elem* tail_1 = NULL;

elem* tail_2 = NULL;

elem* new_head = NULL;

if(phead == NULL || phead->next == NULL) // list size is 0 or 1

{

return phead;

}

int index = 0;

tail_1 = NULL;

tail_2 = phead;

for(; tail_2; tail_2 = tail_2->next)

{

if(index % 2 == 0)

{

tail_1 = (tail_1 == NULL) ? phead : tail_1->next;

}

index++;

}

head_1 = phead;

head_2 = tail_1->next;

tail_1->next = NULL;

head_1 = sort_list(head_1, sort_type);

head_2 = sort_list(head_2, sort_type);

if(new_head == NULL)

{

if(compare_node(head_1, head_2) == sort_type)

{

new_head = head_1;

head_1 = head_1->next;

}

else

{

new_head = head_2;

head_2 = head_2->next;

}

}

elem* cur_ptr = new_head;

while(head_1 != NULL && head_2 != NULL)

{

if(compare_node(head_1, head_2) == sort_type)

{

cur_ptr->next = head_1;

cur_ptr = cur_ptr->next;

head_1 = head_1->next;

}

else

{

cur_ptr->next = head_2;

cur_ptr = cur_ptr->next;

head_2 = head_2->next;

}

}

while(head_1 != NULL)

{

cur_ptr->next = head_1;

cur_ptr = cur_ptr->next;

head_1 = head_1->next;

}

while(head_2 != NULL)

{

cur_ptr->next = head_2;

cur_ptr = cur_ptr->next;

head_2 = head_2->next;

}

cur_ptr->next = NULL;

return phead = new_head;

}

int main()

{

node* nptr = new node();

for(int i = 10000; i >= 1; i--)

{

if(nptr->head == NULL)

{

nptr->head = nptr->tail = new elem();

nptr->head->value = i;

}

else

{

elem* tempPtr = new elem();

tempPtr->value = i;

nptr->tail->next = tempPtr;

nptr->tail = nptr->tail->next;

}

}

nptr->head = sort_list(nptr->head, -1);

elem* temp = nptr->head;

while(temp)

{

cout<<temp->value<<" ";

temp = temp->next;

}

cout<<endl;

return 0;

}