算法学习之分治(合并排序)

 分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之

   分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

 

合并排序就是分治思想的一种体现,合并排序的主要思想是:把两个已经排序好的序列进行合并,成为一个排序好的
序列。例如:13579 2468这两个序列,各自都是排好序的,然后我们进行合并,成为123456789这样一个
排好序的序列。貌似这个跟排序关系不大,因为排序给的是一个乱的序列,而合并是合并的两个已经排序
好的序列。且慢,我们可以把需要排序的数据分解成N个子序列,当分解的子序列所包含数据个数为1的时
候,那么这个序列不久是有序了吗?然后再合并。这个就是有名的”分治“了。。

例如321分成3,2,1三个序列,1这个序列是有序的啦。同理2,3都是有序的。然后我们逐一的合并他们。3,2合并为23,
然后在23与1合并为123。哈哈,排序成功。合并排序主要思路就是这样了。
但是,问题又出来了,怎么合并两个有序列呢?我相信我应该理解了数组的存储方式,所以直接用数组说
事啦。。我们先把下标定位到各有序子序列的开始,也把合并之后数组的下标定位到最初。那么下标对应
的位置就是他们当前的最小值了。然后拿他们来比较,把更小的那个放到合并之后数组的下标位置。这样
,合并后数组的第一个元素就是他们的最小值了。接着,控制合并后数组的下标后移一个,把比较时小数
字所在序列对应的下标后移一个。这样。下次比较的时候,他得到就是他的第二小,(第一下已经合并了
)就是当前最小值了,在于另一个序列的当前最小值比较,用小的一个放到合并后数组的相应位置。依次
类推。接着当数据都合并玩了结束,合并完成。
1357 2468 来做例子:
(1回合)    1357 2468 00000(合并后数据空)
(2)  357 2468 100000(0表示空) 因为1 < 2所以把1放到合并后位置中了(这里1并不是丢掉了,而是下
标变为指向3了,1是没有写而已。呵呵。理解为数组的下标指向了3)
(3) 357 468 120000  因为3 > 2,所以把而放进去
(4) 57 468  123000  同理3 < 4
(5) 57 68   1234000 同理5 > 4
(6) 7 68    1234500 同理5 > 6
(7) 7 8        1234560 同理7 > 6
(8) 0(空了) 8 12345670 同理7 < 8
(9) 0 0 12345678  弄最后一个

当然,这些只是思路。并不是一定一成不变的这样。合并OK,那么我们就可以用合并排序了哦!哈哈。。
不过注意,那个321全部弄成一个单个数字,然后一个一个合并这样来合并似乎不是很好,貌似还有更好
的解决方案。哈哈,对了,就是我先分一半来合并。如果这一半是排好序的,那么合并不久简单了吗?但
是我怎么让一般排好序呢。呵呵简单,我一半在分一半合并排序,在分一半合并排序,直到分到两个都是
1个了,就合并,ok!
例如,81726354:
(1)分成9172 6354 
(2)把8172 分成 81 和72 把6354分成63和54
(3)81分成8和1,哦能合并了哦。合并为18, 同理72,63,54,也可以分解成单个合并为27,36,45
(4) 现在变为了 18, 27, 36, 45了,这个时侯,18 和27能合并了,合并为1278 同理36,合并为45 3456
(5) 好了最好吧,1278和3456合并为12345678.ok排序成功。哈哈。
这样把一个问题分解为两个或多个小问题,然后在分解,最后解决小小问题,已达到解决打问题的目的。
哈哈。分治很强大。哈哈。如果看不懂,我也没有办法啦。。看教科书吧。呵呵
思路主要就是这样了哦:
程序实现上也有点技巧。这个就不说了,直接奉上源代码:

 

1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 //合并排序的合并程序他合并数组nData中位置为[nP,nM) 和[nM,nR).这个是更接近标准的思路
  5 bool MergeStandard(int nData[], int nP, int nM, int nR)
  6 {
  7     int n1 = nM - nP;        //第一个合并数据的长度
  8     int n2 = nR - nM;        //第二个合并数据的长度
  9 
 10     int *pnD1 = new int[n1 + 1];        //申请一个保存第一个数据的空间
 11     int *pnD2 = new int[n2 + 1];        //申请二个保存第一个数据的空间
 12 
 13     for (int i = 0; i < n1; ++i)        //复制第一个数据到临时空间里面
 14     {
 15         pnD1[i] = nData[nP + i];
 16     }
 17     pnD1[n1] = INT_MAX;                    //将最后一个数据设置为最大值(哨兵)
 18 
 19     for (int i = 0; i < n2; ++i)        //复制第二个数据到临时空间里面
 20     {
 21         pnD2[i] = nData[nM + i];
 22     }
 23     pnD2[n2] = INT_MAX;                    //将最后一个数据设置为最大值(哨兵)
 24     
 25     n1 =  n2 = 0;
 26 
 27     while(nP < nR)
 28     {
 29         nData[nP++= pnD1[n1] <  pnD2[n2] ? pnD1[n1++] : pnD2[n2++];        //取出当前最小值到指定位置
 30     }
 31 
 32     delete pnD1;
 33     delete pnD2;
 34     return true;
 35 }
 36 
 37 //合并排序的合并程序他合并数组nData中位置为[nP,nM) 和[nM,nR).
 38 bool Merge(int nData[], int nP, int nM, int nR)
 39 {
 40     //这里面有几个注释语句是因为当时想少写几行而至。看似短了,其实运行时间是一样的,而且不易阅读。
 41 
 42     int nLen1 = nM - nP;        //第一个合并数据的长度
 43     int nLen2 = nR - nM;         //第二个合并数据的长度
 44     int* pnD1 = new int[nLen1];    //申请一个保存第一个数据的空间
 45     int* pnD2 = new int[nLen2];   //申请一个保存第一个数据的空间
 46     
 47     int i = 0
 48     for ( i = 0; i < nLen1; ++i)        //复制第一个数据到临时空间里面
 49     {
 50         pnD1[i] = nData[nP + i];
 51     }
 52 
 53     int j = 0;
 54     for (j = 0; j < nLen2; ++j)        //复制第二个数据到临时空间里面
 55     {
 56         pnD2[j] = nData[nM + j];
 57     }
 58 
 59     i = j = 0;
 60     while (i < nLen1 && j < nLen2)
 61     {
 62         //nData[nP++] = pnD1[i] < pnD2[j] ? pnD1[i++] : pnD2[j++];        //取出当前最小值添加到数据中
 63         
 64         if (pnD1[i] < pnD2[j])        //取出最小值,并添加到指定位置中,如果pnD1[i] < pnD2[j]
 65         {
 66             nData[nP] = pnD1[i];    //取出pnD1的值,然后i++,定位到下一个个最小值。
 67             ++i;
 68         }
 69         else                        //这里同上
 70         {
 71             nData[nP] = pnD2[j];
 72             ++j;
 73         }
 74         ++nP;                        //最后np++,到确定下一个数据
 75     }
 76 
 77     if (i < nLen1)                    //如果第一个数据没有结束(第二个数据已经结束了)
 78     {
 79         while (nP < nR)                //直接把第一个剩余的数据加到nData的后面即可。
 80         {
 81             //nData[nP++] = pnD1[i++];
 82             nData[nP] = pnD1[i];
 83             ++nP;
 84             ++i;
 85         }
 86     }
 87     else                            //否则(第一个结束,第二个没有结束)
 88     {
 89         while (nP < nR)                //直接把第一个剩余的数据加到nData的后面即可。
 90         {
 91             //nData[nP++] = pnD2[j++];
 92             nData[nP] = pnD2[j];
 93             ++nP;
 94             ++j;
 95         }
 96     }
 97 
 98     delete pnD1;        //释放申请的内存空间
 99     delete pnD2;
100 
101     return true;
102 }
103 
104 //合并的递归调用,排序[nBegin, nEnd)区间的内容
105 bool MergeRecursion(int nData[], int nBegin, int nEnd)
106 {
107     if (nBegin >= nEnd - 1)        //已经到最小颗粒了,直接返回
108     {
109         return false;
110     }
111 
112     int nMid = (nBegin + nEnd) / 2;            //计算出他们的中间位置,便于分治
113     MergeRecursion(nData, nBegin, nMid);    //递归调用,合并排序好左边一半
114     MergeRecursion(nData, nMid, nEnd);        //递归调用,合并排序好右边一半
115     //Merge(nData, nBegin, nMid, nEnd);        //将已经合并排序好的左右数据合并,时整个数据排序完成
116     MergeStandard(nData, nBegin, nMid, nEnd);//(用更接近标准的方法合并)
117 
118     return true;
119 }
120 
121 //合并排序
122 bool MergeSort(int nData[], int nNum)
123 {
124     return MergeRecursion(nData, 0, nNum);        //调用递归,完成合并排序
125 }
126 
127 int main()
128 {
129     int nData[10= {4,10,3,8,5,6,7,4,9,2};    //创建10个数据,测试
130 
131     MergeSort(nData, 10);
132     for (int i = 0; i < 10++i)        
133     {
134         printf("%d ", nData[i]);
135     }
136 
137     printf("\n");
138     system("pause");
139     return 0;
140 }
141 

算法学习之分治(合并排序)

上一篇:TreeList用法(1)


下一篇:使用python requests库上传文件时,name和filename乱码问题