一文搞懂分治算法( 二 ) _分治算法

public int searchInsert(int[] nums, int target) { if(nums[0]>=target)return 0;//剪枝 if(nums[nums.length-1]==target)return nums.length-1;//剪枝 if(nums[nums.length-1]<target)return nums.length; int left=0,right=nums.length-1; while (left<right) { int mid=(left+right)/2; if(nums[mid]==target) return mid; else if (nums[mid]>target) { right=mid; } else { left=mid+1; } } return left;}快速排序快排也是分治的一个实例，快排每一趟会选定一个数，将比这个数小的放左面，比这个数大的放右面，然后递归分治求解两个子区间，当然快排因为在分的时候就做了很多工作，当全部分到最底层的时候这个序列的值就是排序完的值。这是一种分而治之的体现。

文章插图

public void quicksort(int [] a,int left,int right){  int low=left;  int high=right;  //下面两句的顺序一定不能混 ， 否则会产生数组越界！！！very important！！！  if(low>high)//作为判断是否截止条件    return;  int k=a[low];//额外空间k ， 取最左侧的一个作为衡量 ， 最后要求左侧都比它小 ， 右侧都比它大 。  while(low<high)//这一轮要求把左侧小于a[low],右侧大于a[low] 。  {    while(low<high&&a[high]>=k)//右侧找到第一个小于k的停止    {      high--;    }    //这样就找到第一个比它小的了    a[low]=a[high];//放到low位置    while(low<high&&a[low]<=k)//在low往右找到第一个大于k的 ， 放到右侧a[high]位置    {      low++;    }    a[high]=a[low];     }  a[low]=k;//赋值然后左右递归分治求之  quicksort(a, left, low-1);  quicksort(a, low+1, right);  }

归并排序(逆序数)快排在分的时候做了很多工作，而归并就是相反，归并在分的时候按照数量均匀分，而合并时候已经是两两有序的进行合并的，因为两个有序序列O(n)级别的复杂度即可得到需要的结果。而逆序数在归并排序基础上变形同样也是分治思想求解。

文章插图

private static void mergesort(int[] array, int left, int right) {  int mid=(left+right)/2;  if(left<right)  {    mergesort(array, left, mid);    mergesort(array, mid+1, right);    merge(array, left,mid, right);  }}private static void merge(int[] array, int l, int mid, int r) {  int lindex=l;int rindex=mid+1;  int team[]=new int[r-l+1];  int teamindex=0;  while (lindex<=mid&&rindex<=r) {//先左右比较合并    if(array[lindex]<=array[rindex])    {      team[teamindex++]=array[lindex++];    }    else {          team[teamindex++]=array[rindex++];    }  }  while(lindex<=mid)//当一个越界后剩余按序列添加即可  {    team[teamindex++]=array[lindex++];  }  while(rindex<=r)  {    team[teamindex++]=array[rindex++];  }   for(int i=0;i<teamindex;i++)  {    array[l+i]=team[i];  }}

最大子序列和最大子序列和的问题我们可以使用动态规划的解法，但是也可以使用分治算法来解决问题，但是最大子序列和在合并的时候并不是简单的合并，因为子序列和涉及到一个长度的问题，所以正确结果不一定全在最左侧或者最右侧，而可能出现结果的区域为：