归并排序.txt

归并排序：将数组划分为小数组,通过局部的有序合并,解决问题 算法平均时间复杂度: O(nlogn)

归并排序
bool MergeSort(int low,int high,int *array)
{
int middle=(high+low)/2;     //将数组划分为2分
if(low<high)
{
  MergeSort(low,middle,array);   //对前一部分进行递归处理
  MergeSort(middle+1,high,array);   //对后一部分进行递归处理
  HeBing(low,middle,middle+1,high,array); //将排序后的,前后两部分,进行合并
}
return true;
}
bool HeBing(int low1,int high1,int low2,int high2,int *array)
{
int *temp,
  i=low1,
  j=low2,
  k=0;
temp=(int *)malloc((high2-low1+1)*sizeof(int));   //temp用于临时存储合并后的数组
while(i<=high1&&j<=high2)        //对两个有序数组进行合并
{
  if(array[i]<array[j])
  {
   temp[k++]=array[i];
   i++;
  }
  else
  {
   temp[k++]=array[j];
   j++;
  } 
}
if(i<=high1)
{
  while(i<=high1)
   temp[k++]=array[i++];
}
else
{
  while(j<=high2)
   temp[k++]=array[j++];
}
for(i=low1,j=0;i<=high2;i++,j++)                        //将合并后的数组,复制到array中
{
  array[i]=temp[j];
}
free (temp);
return true;
}