1.思想
- 分治思想顾名思义，分而治之。我们把一个规模n的问题进行划分为一个一个我们能简单解决的问题，然后合并结果得到n规模问题的解。
2.前提条件
- 第一，n规模的问题划分后的的子问题之间是相同的，即可以用同一个思维，同一套代码解决。
- 第二，这些子问题的解合并后就是原问题的解。
- 第三，子问题之间最好不要包含相同的部分，否则效率会下降。
3.问题
- 合并子问题的解然后得到原问题的解，怎么去实现呢？
如果我手动一个一个去合并，那是不行的。这种方式我们需要预测问题划分的子问题数，代码效率极低。所以递归的使用就是去合并子问题的解。使用递归去不断的划分问题，直到触发划分停止条件。并且递归的使用也是因为我们的子问题是一样的，同一套代码是可以重复解决不同的子问题的，所以使用了递归。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
3.列子
- 快速排序
快速排序取出一个数，然后让序列中数与之比较，小的在它的左边，大的在它的右边。如果我们把这个方式从两组两个数使用，然后再通过同样的方式排序两组数，结果就是这四个数的正确排序结果。所以衍生出了快速排序的方式去解决问题。
private int sort(int l, int r, int [] data){
int curValue = data[l]; //保存要被比较的那个值，然后最后再把它放入那个应该在的位置
while(l < r){ // 外层循环为了不断推进l,r，直到l = r
while(l < r && data[r] > curValue )
r --;
if(data[r] < curValue){
data[l ++ ] = data[r];
}
while(l < r && data[l] < curValue )
l ++;
if(data[l] > curValue){
data[r -- ] = data[l];
}
}
data[l] = curValue; //最后l = r的时候，这个位置就是被比较的值的最终位置
return l;
}
private void mergeSort(int l, int r, int [] data){
//先排序，再拆分
if(l < r){
int cur = sort(l,r,data);
mergeSort(l,cur-1,data);
mergeSort(cur+1,r,data);
}
}
代码中需要注意的地方是交换的方式有些特别，平交换我们是首先把一个值保存到临时的变量，然后把另一个值赋值给前一个值，最后把临时变量的值赋予后一个值。但是在代码中每一个的交换都没有去做最后一步，这可以理解为，交换了第一次后，虽然没有把临时变量赋值到交换的位置，假装它在那个位置，反正继续向后走，那个位置还会被需要交换的值覆盖，如此我只要把这个临时变量赋值给最后的那个位置，我就做了它和好几个的变量的交换。
- 归并排序
归并排序的思想也是分治，它是先拆分再排序和快速排序是相反的。它的做法是，我把一个序列拆分为两个序列，然后使用第一个序列的，第一个值取比较第二个序列的第一个值，然后小的放入新数组，两个序列被取过的序列，游标向前一步，直到其中一个序列取完，另一个序列的剩余部分自动补到新数组中。如果这两个序列都是有序的，那么这样操作就结果就是排序好的一个数组了。如果我们使用这种思维，从最小的两个数，划分两个序列进行比较，然后再合并再和其他同样方式的序列进行这样的方式。那么一个规模为n的问题就不是问题了，所以出现了归并。
private void mergeSort(int l, int r,Integer [] data){
//先拆分，再排序
if(l < r){
int mid = (l + r)/2;
mergeSort(l,mid,data);
mergeSort(mid+1,r,data);
sort(l,r,data);
}
}
private void sort(int l, int r, Integer [] data){
int center = (l + r)/2;
int ll = l;
int lr = center;
int rl = center +1;
int rr = r;
Integer[] temp = new Integer[data.length]; //需要和原数组一样长，在复制回去的时候，才能按原来的位置来复制
int tempIndex = ll;//起始的位置是l,也是因为上面的原因
while(ll < lr +1 && rl < rr+1){ //加1是为了最后一个数不被忽略
if(data[ll] < data[rl]){
temp[tempIndex ++ ] = data[ll ++];
}else {
temp[tempIndex ++ ] = data[rl ++];
}
}
//如果有一边没有比较，那么直接顺延的数组
while(ll < lr +1){
temp[tempIndex ++] = data[ll ++];
}
while(rl < rr+1){
temp[tempIndex ++] = data[rl ++];
}
System.arraycopy(temp,l,data,l,r-l+1);
}
网友评论