亲宝软件园·资讯

展开

Java分治算法

LNORA 人气:0

分治算法

什么是分治算法

顾名思义就是分而治之,分治法可以用来解决各种问题,是一种将复杂难解的问题分割成规模和结构相同或者相似的子问题,通过对简单子问题的求解而达到对原问题的求解目的的算法设计方法,在求解一个复杂问题时可以将其分解成若干个子问题,子问题还可以进一步分解成更小的子子问题,直到解决的子问题是一些基本的问题,并且求解方法是已知的,可以直接求解为止。分而治之的策略不但能够使原本复杂的问题变得更加清晰,而且能够将问题的规模缩小而降低问题求解的难度。

分治算法的思想

对于一个规模较大的问题,可以将这个规模较大的问题分解为n个规模较小的相互独立且与原问题结构相同的子问题进行求解。首先通过递归来解决这些子问题,然后对子问题的解进行合并得到原问题的解,这中求解问题的思路就是分治法。

简单可以理解为

首先将原问题分解为若干个子问题

各子问题的结构基本相似,规模基本相当

递归使分治的工具

分治法四大基本特征

分治法求解问题的三个基本步骤

分治算法解决问题过程的伪代码

 divide-and-conquer(p)//阀值
 {
     if(|p|<n0)adhoc(p);//如果问题可以直接求解,就直接求解。|p|代表问题的规模
     divide p into amaller subinstances P1,P2,P3......Pk;//将原问题分解成k个规模较小的子问题,且这些子问题的规模相当结构相似
     for(i=1;i<=k;i++)
         yi=divide-and-conquer(p)//递归求解各个子问题Pi,若分解的子问题还可以分解成若干个子子问题,就再对子问题进行分解
         return merge(y1,y2,y3......yk)//将子问题的解合并成原问题的解
 }  

关于分治算法的举例

归并排序

归并排序算法是用分治策略实现对规模为n的记录序列进行排序的算法,基本思想是:待排序记录分成大小大致相同的两个或多个子集合,分别对子集合进行排序,最终将两个排序号的子集合合并成所要求的排序好的集合。

package 算法设计与分析;
 public class 归并排序 {
 //arr是存放原始元素的数组,left数组arr的最左边,left是数组的最右边,mid是划分的终点,数组tmp是一个临时数组,就是一个辅助存储空间
         public static void main(String[] args) {
             int[] arr = {49,38,65,97,76,13,27};
             int[] tmp = new int[arr.length];    //新建一个临时数组存放,相当于是一个辅助空间
             mergeSort(arr,0,arr.length-1,tmp);
             for(int i=0;i<arr.length;i++){
                 System.out.print(arr[i]+" ");
             }
         }
         public static void merge(int[] arr,int left,int mid,int right,int[] tmp){
             int i = 0;
             int j = left,k = mid+1;  //左边序列和右边序列起始索引
             while(j <= mid && k <= right){
                 if(arr[j] <= arr[k]){
                     tmp[i++] = arr[j++];
                 }else{
                     tmp[i++] = arr[k++];
                 }
             }
             //若左边序列还有剩余,则将其全部拷贝进tmp[]中
             while(j <= mid){
                 tmp[i++] = arr[j++];
             }
             while(k <= right){
                 tmp[i++] = arr[k++];
             }
             for(int t=0;t<i;t++){
                 arr[left+t] = tmp[t];
             }
         }
         public static void mergeSort(int[] arr,int left,int right,int[] tmp){
             if(left<right){
                 int mid = (left+right)/2;
                 mergeSort(arr,left,mid,tmp); //对左边序列进行归并排序
                 mergeSort(arr,mid+1,right,tmp);  //对右边序列进行归并排序
                 merge(arr,left,mid,right,tmp);    //合并两个有序序列,相当于用tmp覆盖原来的arr
             }
         }
     }

基本步骤

快速排序

快速排序又称为交换排序,是冒泡排序的一种,在快速排序中,记录的比较和交换是从两端向中间进行的,关键字值较大的记录一次就能交换到后面单元,关键字值小的记录一次就能交换到前面单元,记录每次移动的距离较大,因而总的比较和移动次数较少。

思想:把最左边的元素作为主元,数组一左一右两个指针进行扫描,左边的指针直到找到一个元素比主元大时,便停止左移,右边的指针向左移动,直到找到一个不大于主元的元素,交换两个指针所指向的元素。

注意:这种排序要在左边设置一个较大的值作为哨兵,防止左指针在右移的过程中移出序列之外。

package 算法设计与分析;
 public class 快速排序 {
         public static void quickSort(int[] arr,int left,int right){
             int i,j,temp,t;
             if(left>right){
                 return;
             }
             i=left;
             j=right;
             //temp就是基准位,就是主元,将数组中的第一个元素作为主元
             temp = arr[left];
             while (i<j) {
                 //先看右边,依次往左递减
                 while (temp<=arr[j]&&i<j) {
                     j--;
                 }
                 //再看左边,依次往右递增
                 while (temp>=arr[i]&&i<j) {
                     i++;
                 }
                 //如果满足条件则交换
                 if (i<j) {
                     t = arr[j];
                     arr[j] = arr[i];
                     arr[i] = t;
                 }
             }
             //最后将基准为与i和j相等位置的数字交换
             arr[left] = arr[i];
             arr[i] = temp;
             //递归调用左半数组
             quickSort(arr, left, j-1);
             //递归调用右半数组
             quickSort(arr, j+1, right);
         }
         public static void main(String[] args){
             int[] arr = {72,26,57,88,42,80,72,48,60,};
             quickSort(arr, 0, arr.length-1);
             for (int i = 0; i < arr.length; i++) {
                 System.out.print(arr[i]+ " ");
             }
         }
     }

二分搜索算法

在一个表中搜索确定一个关键字值为给定的元素,若在表中存在这样的元素,则搜索成功,搜索结果可以返回整个数据的元素,也可以指示该元素在表中的位置,若表中不存在关键字值的元素,则搜索失败。

 package 算法设计与分析;
 //用递归的方法解决二分搜索问题
 public class 二分查找 {
     public static void main(String[] args) {
         int[] arr = {-7,-2,0,15,27,54,80,88,102};
         //想要查找的元素
         int key = 80;
         //对查找到的元素进行定位
         int position = Search(arr,key,0,arr.length - 1);
         if(position == -1){
             System.out.println("查找的是"+key+",序列中没有该数!");
         }else{
             System.out.println("查找的是"+key+",找到位置为:"+position);
         }
     }
     public static int Search(int[] arr,int key,int left,int right){
         if(key < arr[left] &&key > arr[right] &&left > right){
             return -1;
         }
         int middle = (left + right) / 2;            //初始中间位置
         if(arr[middle] > key){
             //比关键字大则关键字在左区域
             return Search(arr, key, left, middle - 1);
         }else if(arr[middle] < key){
             //比关键字小则关键字在右区域
             return Search(arr, key, middle + 1, right);
         }else {
             return middle;
         }
     }
 }

小结

以上就是针对分治算法的详细分析,分治算法在我们解决问题的过程中可以使我们的问题变得简单化,降低时间复杂度,利用分治法解决问题比较稳定。

加载全部内容

相关教程
猜你喜欢
用户评论