归并排序

真的没有想到，以前不曾关注的归并排序原来是这么的复杂。其实，快速排序、堆排序以及归并排序都用到了递归思想，难点就是找出递归形式和递归出口。然而，归并排序还是实际中能够应用到的一种算法--分布式处理。因为，现实中，数据量会比较大，超出一台计算机的内存上限是可能的，这就需要将数据分配到若干台计算机上并行计算。这和现在正在学习的hadoop又不谋而合，因此，现在来学一下归并排序。

对于归并排序，因为所选的数据结构不同，它的实现也不大相同，但原理上还是一样的。都是先将数据一分再分，直到有序为止（也就是每个分项中只有一个元素的时候），然后两两开始合并，直至合并为一个有序项为止。

下面先看看它的数组结构下的实现吧

//合并数组
void MergeArray(int[] a, int first, int second, int length, int[] temp){
  int i = first,j = second,t = 0;
  while(i < second && j < length){
     if(a[i] < a[j])
        temp[t++] = a[i++];
     else
        temp[t++] = a[j++];
   }
   while(i < second)
      temp[t++] = a[i++];
   while(j < length)
      temp[t++] = a[j++];
   i = first;
   while(i < length)
      a[i++] = temp[i-first];
}

//元素排序
void mergeSort(int[] a,int low, int length,int[] temp){
   if(low < length){
       int mid = (low + length) / 2;
       mergeSort(a, low, mid);
       mergeSort(a,mid, length);
       MergeArray(a,low,mid,length,temp);
    }
} 

void MergeSort(int[] a, int length){
   int[] temp = new int[length];
   int low = 0;
   mergeSort(a,low,length);
   delete[] temp;
}

 下面是链表结构的排序:

//结构体定义
struct node{
  int data;
  node* next;
};
//合并链表
node* MergeLink(node* link1,node link2){
  if(!link1)
    return link2;
  if(!link2)
    return link1;
  node* temp;
  if(link1->data < link2->data){
    temp = link1;
    link1 = link1->next;
  }
  else {
    temp = link2;
    link2 = link2->next;
  }
    temp->next = MergeLink(link1,link2);
    return temp;
}

node* MergeSort(node* link){
 if(!link)
    return NULL;
 if(!link->next)
    return link;
  node* link1 = link;
  node* link2 = link;
  node* Link = link;
  //将链表分成两份
  while(link2->next&&link2->next->next){
    link1 = link1->next;
    link2 = link2->next->next;
  }
  link2 = link1->next;
  link1->next = NULL;
  Link = MergeLink(MergeSort(link1),MergeSort(link2));
  return Link;
}