合并排序

1682阅读　0评论2012-09-29　tansijie
分类：C/C++

合并排序的原理就是使用分治法策略，将一个规模为N的问题，划分为n个规模为m（mvoid MergerSort(int* _array,int left,int right)
{
    if(left
    {
         int middle=(left+right)/2;
 MergerSort(_array,left,middle);
 MergerSort(_array,middle+1,right);
         MergerArray(_array,left,right);

    }

}
C语言代码如下：

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. //数组合并
  3. void MergeArray(int* sorce , int left ,int right)
  4. {
  5.     int k = 0 ;
  6.     int i = left ;
  7.     int middle = (left+right)/2;
  8.     int j = middle+1;
  9.     int* dest = new int[right-left+1];
  10.     while(i<=middle&& j<=right)
  11.     {
  12.         if(sorce[i]<sorce[j])
  13.         {
  14.             dest[k++] = sorce[j++];
  15.         
  16.         }else
  17.         {
  18.             dest[k++] = sorce[i++];
  19.             
  20.         }
  21.     }
  22.     while(i<=middle)
  23.     {
  24.         dest[k++] = sorce[i++];
  25.     }
  26.     while(j<=right)
  27.     {
  28.         dest[k++] = sorce[j++];
  29.     }
  30.     //将合并好的结果和源数组进行交换，相当于拷贝
  31.     int q = left ;
  32.     int m = 0 ;
  33.     while( q<=right)
  34.     {
  35.         sorce[q++] = dest[m++];
  36.     }
  37.     delete[] dest;
  38. }

  40. //合并排序
  41. void MergeSort(int* _array,int left,int right)
  42. {
  43.     if(left<right)
  44.     {
  45.         int middle = (left+right)/2;

  47.         MergeSort(_array,left,middle); //对左边排序
  48.         MergeSort(_array,middle+1,right);//对右边排序
  49.         //对排序结果进行合并    
  50.         MergeArray(_array,left,right);
  51.     }
  52.     
  53. }
  54. int main(int argc, char** argv)
  55. {
  56.     

  58.     int _wait_array[7] ={24,-2,11,9,31,0,21};

  60.     MergeSort(_wait_array,0,6);

  62.     return 0 ;

  64. }



上一篇：折半查找递归
下一篇：Oracle Max函数产生的怪异问题