归并排序的概念和原理我就不介绍了，网上的相关资料一箩筐。在这里，我只想记录一个思路，归并的排序分为三步走：1 分割，2 递归，3 合并。下面我将分别针对数组和链表两种情况的归并排序，写一下程序和思路。关于链表的归并排序，这个题目我在网易有道的面试中经历过。当时蒙住了，因为绝大多数的数据结构的书，以及算法的书介绍归并排序的时候往往都是以数组为例的。
数组归并排序代码：
/*
**归并排序三步走：1 分割子问题；2 递归；3 合并子问题。
*/
#include "stdafx.h"
#include <iostream>
using namespace std;
void mergeArray(int *a, int begin1, int length1, int begin2, int length2)
{
int length = length1 + length2;
int begin = begin1;
int *b = new int[length];
int pos = 0;
int cur1 = begin1;
int cur2 = begin2;
while((cur1 - begin1 + 1) <= length1 && (cur2 - begin2 + 1) <= length2)
{
if(a[cur1] <= a[cur2])
{
b[pos] = a[cur1];
cur1++;
pos++;
}
else
{
b[pos] = a[cur2];
cur2++;
pos++;
}
}
//前半段的数组已经合并完毕，可以直接将后半段的数组复制到数据b
if((cur1 - begin1 + 1) > length1)
{
while((cur2 - begin2 + 1) <= length2)
{
b[pos] = a[cur2];
cur2++;
pos++;
}
}
else if((cur2 - begin2 + 1) > length2)
{
while((cur1 - begin1 + 1) <= length1)
{
b[pos] = a[cur1];
cur1++;
pos++;
}
}
//将合并后的数组b复制给数据a
for(int i = 0; i < length; i++)
{
a[begin] = b[i];
begin++;
}
}
void mergeSort(int *a, int left, int right)
{
if(left >= right)
return;
int mid = left + (right - left)/2;
mergeSort(a, left, mid);
mergeSort(a, mid+1, right);
int length1 = mid - left + 1;
int length2 = right -(mid + 1) + 1;
mergeArray(a, left, length1, mid + 1, length2);
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[5] = {3, 5, 1, 2, 7};
//int a[5] = {1,1,2,1,1};
mergeSort(a, 0, 4);
for(int i = 0; i < 5; i++)
{
cout<<a[i]<<" ";
}
getchar();
return 0;
}
对链表进行归并排序的代码如下：
struct node
{
int data;
node * next;
};
/*
**对两个有序链表进行归并
*/
node *MergeList(node *head1, node *head2)
{
node * tmp;
if(head1 == NULL)
return head2;
if(head2 == NULL)
return head1;
if(head1->data < head2->data)
{
tmp = head1;
head1 = head1->next;
}
else
{
tmp = head2;
head2 = head2->next;
}
tmp->next = MergeList(head1, head2);
return tmp;
}
/*
**归并排序，参数为要排序的链表的头结点，函数返回值为排序后的链表的头结点
*/
node *MergeSort(node *head)
{
if(head == NULL)
return 0;
node * r_head = head;
node *head1 = head;
node* head2 = head;
while(head2->next != NULL && head2->next ->next!= NULL)
{
head1 = head1->next;
head2 = head2->next->next;
}
if(head1->next == NULL)/*说明只有一个节点，则返回该节点*/
return r_head;
head2 = head1->next;
head1->next = NULL;
head1 = head;
/*函数MergeList是对两个有序链表进行归并，返回值是归并后的链表的头结点*/
r_head = MergeList(MergeSort(head1), MergeSort(head2));
return r_head;
}