C++ 之“合并排序”代码

鉴客 发布于 2010/05/22 08:42
阅读 379
收藏 1

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

下面是代码:

#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;
}

加载中
返回顶部
顶部