合并排序C++代码

合并排序C++代码

合并排序的单向链表实现并不是最快的方法，对于100万个数，合并排序单向链表的实现用时15秒，比合并排序的数组实现（1.2秒）和快速排序的数组实现（0.4秒）都要慢。但是有些应用不得不适用链表，而快速排序法由于涉及太多的random access，用链表实现显然会非常的慢。所以单向链表的合并排序的应用也是很广泛的。

以下是我的C/C++代码：

// merge sort on linked list

// by Qingxing Zhang, Dec 26, 2009. prep for google interview

#include <iostream>
#include <time.h>
#include <stdlib.h>
#define N 1000000
using namespace std;

struct node
{
int data;
node *next;
};

node *insert(node *head, int data)
{
node *tmp = new node;
tmp->data = data;
tmp->next = head;
return tmp;
}

node *remove(node *head)
{
if(head!=NULL)
{
   node *tmp = head;
   head = head->next;
   delete tmp;
}
return head;
}

node *reverse(node *head)
{
node *newHead = NULL;
while(head!=NULL)
{
   node *tmp = head->next;
   head->next = newHead;
   newHead = head;
   head = tmp;
}
return newHead;
}

node *mix(node *left, node *right)
{
node *result = NULL;
while((left!=NULL)&&(right!=NULL))
{
   if(left->data < right->data)
   {
    result = insert(result, left->data);
    left = remove(left);
   }
   else
   {
    result = insert(result, right->data);
    right = remove(right);
   }
}
while(left!=NULL)
{
   result = insert(result, left->data);
   left = remove(left);
}
while(right!=NULL)
{
   result = insert(result,right->data);
   right = remove(right);
}
result = reverse(result);
return result;
}

node *merge(node *head, int n)
{
if(n==1)
   return head;
// divide into 2 lists
node *right = head;
node *left = head;
for(int i=0;i<n/2-1;i++)
   right = right->next;
node *tmp = right;
right = right->next;
tmp->next = NULL;
// do merge sort on both lists
left = merge(left,n/2);
right = merge(right,n-n/2);
// mix left and right
return mix(left,right);
}

int main()
{
clock_t start,end;
double diff;
node *head = NULL;
srand ( (unsigned int)time(NULL) );
for(int i=0;i<N;i++)
   head = insert(head,rand());

start = clock();
head = merge(head,N);
end = clock();
diff = end - start;
cout << "Merge sort for linked list: " << diff/CLOCKS_PER_SEC << " seconds..." << endl;

//while(head!=NULL)
//{
// cout << head->data << endl;
// head = head->next;
//}

return 0;
}