CodeBeauty
春暖花开
posts - 6,comments - 3,trackbacks - 0
经典排序算法-归并排序MergeSort
归并排序(Merge sort,即合并排序)
是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。其时间复杂度为O(n)O(最优)、(nlog n)(最差)。

算法描述

归并排序具体工作原理如下(假设序列共有n个元素):

  1. 将序列每相邻两个数字进行归并操作,形成floor(n/2)个序列,排序后每个序列包含两个元素
  2. 将上述序列再次归并,形成floor(n/4)个序列,每个序列包含四个元素
  3. 重复步骤2,直到所有元素排序完毕
 

其中一次归并操作的过程如下:

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  4. 重复步骤3直到某一指针达到序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾
    #include <iostream>
    using namespace std;

     
    //合并排序的合并程序他合并数组nData中位置为[nP,nM) 和[nM,nR).这个是更接近标准的思路
     bool MergeStandard(int nData[], int nP, int nM, int nR)
     
    {
         
    int n1 = nM - nP;        //第一个合并数据的长度
         int n2 = nR - nM;        //第二个合并数据的长度
     
         
    int *pnD1 = new int[n1 + 1];        //申请一个保存第一个合并数据的空间
         int *pnD2 = new int[n2 + 1];        //申请一个保存第二个合并数据的空间
     
         
    for (int i = 0; i < n1; ++i)        //复制第一个数据到临时空间里面
         {
             pnD1[i] 
    = nData[nP + i];
         }

         pnD1[n1] 
    = INT_MAX;                    //将最后一个数据设置为最大值(哨兵)
     
         
    for (i = 0; i < n2; ++i)        //复制第二个数据到临时空间里面
         {
             pnD2[i] 
    = nData[nM + i];
         }

         pnD2[n2] 
    = INT_MAX;                    //将最后一个数据设置为最大值(哨兵)
         
         n1 
    =  n2 = 0;
     
         
    while(nP < nR)
         
    {
             nData[nP
    ++= pnD1[n1] <  pnD2[n2] ? pnD1[n1++] : pnD2[n2++];        //取出当前最小值到指定位置
         }

     
         delete []pnD1;
         delete []pnD2;
         
    return true;
     }


     
    //合并的递归调用,排序[nBegin, nEnd)区间的内容
     bool MergeRecursion(int nData[], int nBegin, int nEnd)
     
    {
         
    if (nBegin >= nEnd - 1)        //已经到最小颗粒了,直接返回
         {
             
    return false;
         }

     
         
    int nMid = (nBegin + nEnd) / 2;            //计算出他们的中间位置,便于分治
         MergeRecursion(nData, nBegin, nMid);    //递归调用,先合并排序好左边一半
         
         MergeRecursion(nData, nMid, nEnd);        
    //递归调用,后合并排序好右边一半
        
    // Merge(nData, nBegin, nMid, nEnd);        //将已经合并排序好的左右数据合并,时整个数据排序完成
         MergeStandard(nData, nBegin, nMid, nEnd);//(用更接近标准的方法合并)
         
    //Output(nData,nEnd);
         return true;
     }

     
     
    //合并排序
     bool MergeSort(int nData[], int nNum)
     
    {
        
    return MergeRecursion(nData, 0, nNum);        //调用递归,完成合并排序
    }


     
    //////////排序后输出函数
     int Output(int b[],int length)
     
    {
         
    for (int i=0;i<length;i++)
         
    {
             cout
    <<b[i]<<"  ";
         }

         cout
    <<endl;
         
    return 1;
    }

     
    int main()
     
    {
         
    //int nData[10] = {4,10,3,8,5,0,7,4,0,2};    //创建10个数据,测试
         int size_nData;
         cout
    <<"Enter the numble of nData: size_nData=";
         cin
    >>size_nData;
         cout
    <<endl<<"Enter nData(size_a values):";
         
    int* nData=new int[size_nData];
         
    for (int i=0;i<size_nData;i++)
         
    {
             cin
    >>nData[i];
         }


         MergeSort(nData, size_nData);
         Output(nData, size_nData);
     
         delete []nData;
         
    return 0;
     }

 

 

 

posted on 2012-05-11 13:32 代码之美 阅读(1519) 评论(0)  编辑 收藏 引用 所属分类: 经典排序算法(C/C++实现)

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理