递归 —— 二分查找法 —— 归并排序

PS:什么是递归、二分查找、归并排序。

递归排序大家都不陌生,递归简单的说就是自己在没有达到目的的同时在此调用本身,把一个大问题层层转化为和原问题相似的小问题解决,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

如果想了解更多可以去百度百科查阅即可。下面是简单例子

1、二分查找法

思路

二分法就是把一个数组折半查找,再折半直到找到数据位置,或者无数据位置。比如说1-100,你选的值是23,那么范围写法就是(索引写法类似)

第一次折半是1-50,51-100,经过查找23<50,是在1-50里。

第二次是1-25,26-50,经过查找23<25,是在1-25里。

..........

使用条件

必须是有序数据

升序和降序start角标和end角标写法相反

/\*\*

     \* 方法描述:二分查找方法

     \* \*\*/

    public static int twoQueryMethod(int[] data,int query){

        int start=0;                //开始角标

        int end=data.length-1;        //结束角标

        int moddle;

        while(true){

            moddle=(end+start)/2;

            if(data[moddle] == query){

                return moddle;

            }

            //起始角标  >  最后角标   没有找到

            else if(start > end){

                return data.length;

            }

            else{

                //中间值大于查找值

                if(data[moddle] > query){

                    end = moddle-1;

                }else{

                    start = moddle + 1;

                }

            }

        }

    }

上面是用平常的while循环写的,下面用递归的写法。

2:递归---二分查找法

使用递归可以取消while的循环使用

/\*\*

     \* 递归取代while循环

     \* 

     \* \*\*/

     //降序查找

    public static int diGuiMethod(int[] data,int search,int start,int end){

        //获取中间值角标

        int moddle=(start+end)/2;

        if(data[moddle] == search){

            return moddle;

        }else if(start > end){

            return data.length;

        }else{

        //下面是降序

            if(data[moddle]< search){

                return diGuiMethod(data,search,start,moddle-1);

            }else{

                return diGuiMethod(data, search, moddle+1, end);



            }

        }

        

    }

    

    //升序查找

    public static int binarySearch(int[] arr, int data, int beginIndex, int endIndex) {

        int midIndex = (beginIndex + endIndex) / 2;

        if (data < arr[beginIndex] || data > arr[endIndex] || beginIndex > endIndex) {

            return -1;

        }

        if (data < arr[midIndex]) {

            return binarySearch(arr, data, beginIndex, midIndex - 1);

        } else if (data > arr[midIndex]) {

            return binarySearch(arr, data, midIndex + 1, endIndex);

        } else {

            return midIndex;

        }

    }

效率

普通二分查找法和递归二分查找都是 O(logN) 但是资料显示 递归二分查找简介但稍微慢一点。

扩展--分治算法

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。即一种分目标完成程序算法,简单问题可用二分法完成。

分治算法--基本思想

当我们求解某些问题时,由于这些问题要处理的数据相当多,或求解过程相当复杂,使得直接求解法在时间上相当长,或者根本无法直接求出。对于这类问题,我们往往先把它分解成几个子问题,找到求出这几个子问题的解法后,再找到合适的方法,把它们组合成求整个问题的解法。如果这些子问题还较大,难以解决,可以再把它们分成几个更小的子问题,以此类推,直至可以直接求出解为止。这就是分治策略的基本思想。

3:归并排序

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

归并排序的条件、使用优点

通过两个不同的有序数组,互相比较按照比较大小排序

把一个无序的数组分成N个数据,每个数据本身比较一次,之后再和下一个数组比较并合并,以此类推。

3.1:两个A,B不同的(有序)数组归并成一个C数组,结果C还是有序的。

public static void mergeTwo(int[] arr1,int[] arr2,int[] mergeArr){

        int aIndex=0,bIndex=0,mIndex=0;

        //两个数组都有数据时

        while(aIndex < arr1.length && bIndex < arr2.length){

            if(arr1[aIndex]<arr2[bIndex]){

                mergeArr[mIndex++] = arr1[aIndex++];

            }else{

                mergeArr[mIndex++] = arr2[bIndex++];

            }

        }

        //如果两个数组长度相等,则下方方法就不会执行,如果A长度大于B,则会走第一个while。

        //两个数组其中一个无数据时

        while(aIndex < arr1.length){

            mergeArr[mIndex++] = arr1[aIndex++];

        }

        while(bIndex < arr2.length){

            mergeArr[mIndex++]=arr2[bIndex++];

        }

        //遍历结果

        for(int i=0;i<mergeArr.length;i++){

            System.out.println(mergeArr[i]);

        }

    }

使用

//main方法中使用

    int[] arr1={12,14,15,16};

        int[] arr2={8,22,56,90,100};

        int [] merge=new int[9];

        mergeTwo(arr1, arr2, merge);

3.2:归并算法--排序一个无需数组

/\*\*

     \* 一个数组内部进行排序

     \* 

     \* \*\*/

    public static void mergeOne(int arr[],int startInt,int stopInt,int[] cArr){

        //如果范围是1则直接返回。

        if(stopInt==startInt){

            return;

        }

        else{

            int middle=(startInt+stopInt)/2;

            //开始把数组分开---二分法

            mergeOne(arr, startInt, middle,cArr);

            mergeOne(arr, middle+1, stopInt,cArr);

            mergeTwoSort(arr,startInt,middle,stopInt,cArr);    

        }

    }

    public static void mergeTwoSort(int arr[],int start,int mid,int end,int[] cArr){

        int left=start;//左序列开始角标

        int right=mid+1;//右序列开始角标

        int cIndex=0;//临时数组

        //当两边都有值时执行

        while(left <= mid&& end>=right){

            //比较两个数组的元素大小,如:A:left=0开始到3,长度为4,B:right=4开始,长度为4,

            if(arr[left]<arr[right])

            {

                cArr[cIndex++]=arr[left++];

            }else{

                cArr[cIndex++]=arr[right++];

            }

        }

        //当右边数组无元素时执行

        while(left<=mid){

            cArr[cIndex++]=arr[left++];

        }

        //当左边数组无元素时执行

        while(right<=end){

            cArr[cIndex++]=arr[right++];

        }

        //将临时数组全部添加进原数组

        cIndex=0;//指针修改为0

        while(start<=end){

            arr[start++]=cArr[cIndex++];

        }

    }

使用

//mian方法使用

//一个数组内部排序

        int[] arr3={12,4,34,5,6,45,9};

        int[] cArr=new int[7];

        mergeOne(arr3, 0, 6, cArr);

        System.out.println("一个数组内部排序");

        for(int i=0;i<cArr.length;i++){

            System.out.println(cArr[i]);

归并效率

O(log2\N)以2为底N的对数。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏LeetCode

LeetCode <Stack>84&85. Maximal Rectangle&Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the ...

1495
来自专栏IT可乐

JDK1.8源码(八)——java.util.HashSet 类

  在上一篇博客,我们介绍了 Map 集合的一种典型实现  HashMap  ,在 JDK1.8 中,HashMap 是由 数组+链表+红黑树构成,相对于早期版...

1182
来自专栏desperate633

LintCode 线段树系列问题(线段树的构造,线段树的构造||,线段树的查询,线段树的查询II,线段树的修改)线段树的构造线段树的构造 II线段树的查询线段树查询 II线段树的修改

线段树是一棵二叉树,他的每个节点包含了两个额外的属性start和end用于表示该节点所代表的区间。start和end都是整数,并按照如下的方式赋值:

843
来自专栏技术博客

C#基础知识系列十(集合)

  本节主要是来了解学习集合,以方便在程序编写时,什么地方该选用什么集合,让程序更健壮的运行起来。在学习了解集合之前,首先需要了解一些数据结构方面的知识。下面我...

1233
来自专栏F_Alex

数据结构与算法(五)-线性表之双向链表与双向循环链表

前言:前面介绍了循环链表,虽然循环链表可以解决单链表每次遍历只能从头结点开始,但是对于查询某一节点的上一节点,还是颇为复杂繁琐,所以可以在结点中加入前一个节点的...

1582
来自专栏desperate633

LintCode 二分查找题目分析代码

给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组...

932
来自专栏禁心尽力

Set容器--HashSet集合

Set容器特点: ①   Set容器是一个不包含重复元素的Collection,并且最多包含一个null元素,它和List容器相反,Set容器不能保证其元素的顺...

2225
来自专栏Python爱好者

Java基础笔记17

1516
来自专栏一个会写诗的程序员的博客

《Kotlin 极简教程 》第5章 集合类(1)

本章将介绍Kotlin标准库中的集合类,我们将了解到它是如何扩展的Java集合库,使得写代码更加简单容易。如果您熟悉Scala的集合库,您会发现Kotlin跟S...

1182
来自专栏JavaEdge

LinkedHashMap源码分析(基于Java8)概要示例代码节点构造函数增删查遍历

4175

扫码关注云+社区

领取腾讯云代金券