【算】选择排序和二分查找

endless_road 发布于2019-08-15 14:50 / 2642人阅读

摘要：劣势二分法快则快矣，但是有个很大的限制，只能用于有序集合的查找。如果本身是一个无序的集合，只能先排序再强行二分。其它还有就是，已经为我们实现了二分查找，详见。

序

大概半个月前，偶尔看到《算法图解》，没翻几页便被数学战五渣的我奉为神书，怎一个相见恨晚、爱不释手加老泪纵横啊！遂写文以作积累……

选择排序 思路

选择排序的思路很好理解，以从小到大排序为例：

选出集合中最小的元素，置于目标集合第一个位置

重复上述过程，剩余元素中选出最小的元素，置于目标集合第二个位置……以此类推，直到最后一个元素.

代码示例

PositionBean类

示例将对int[]进行排序，为了方便处理 int[] 数组 中的索引信息，构建了PositionBean类。（后续的探讨其它算法的文章中，也多以int[]为例，同样会用到PositionBean）

public class PositionBean {
    int val;    //值
    int index;  //索引

    public PositionBean(int val, int index) {
        this.val = val;
        this.index = index;
    }
    
    //省略setter和getter方法……
}

算法实现

查找最小值方法

private static PositionBean findMin(int source[]){
    int minIndex = 0;
    int min=source[minIndex];    //最小值min，初始化为第一个元素
    for(int i=1,len=source.length;isource[i]){    
            min=source[i];
            minIndex = i;
        }
    }

    return new PositionBean(min,minIndex);
}

选择排序实现

public static int[] doOrder(int source[]){
    if(source==null || source.length==0){
        return source;
    }

    int len=source.length;
    int res[] = new int[len];
    for(int i=0;i
移除数组指定元素的方法
/**
 * 移除source[]中，索引为index的元素
 * @param source
 * @param index
 * @return
 */
private static int[] removeElement(int source[],int index){
    int len = source.length;
    int res[] = new int[len-1];
    int resIndex =0;
    for(int i=0;i

代码很简单，不多做解释。
二分查找
思路
大家以前玩没玩过猜数游戏？一个人（张三）先写下1到100的数字中任意一个数，另一个人（李四）去猜，张三根据对方的猜测情况提示“大了”、“小了”，直到猜对！
线性
李四可以选择从1开始猜，接下来的剧情会是这样的：
李：1
张：小了
李：2
张：小
……
这种猜法，最多猜100次。也就是说，最坏情况做了集合遍历，时间复杂度记作O(n)
折半
当然李四也有另外的选择：
李：50
张：小了
李：25
张：大了
……
小李子每次都选择了中间的数字进行猜，而通过张三的提示，每次都能排除当前集合近半的不符合条件的数字：将当前集合（1~100）以 中间数字 进行分隔，要么在数字较小的结合中（1~50），要么在数字较大的集合中（51~100）。
这种方式，就是我们要探讨的二分查找，也叫折半查找。给出示意图：

第一次比较后，由于目标值大于中间数（target=10 > 中间数=8），因此中间数左侧（含中间数）数字-1,1,5,8已然出局（图中第二次比较，将出局的数字格画成了虚线）
代码示例
依照上面的示意图写出代码：
/**
 * 在source[]中寻找target，如果找不到抛出异常RuntimeException(target+"不存在")
 * @param target
 * @param source
 * @return
 */
public static int doFind(int target,int source[]){
    if(source==null || source.length==0){
        throw new RuntimeException("集合为空");
    }
    int low = 0;
    int height = source.length-1;
    do{
        int halfIndex = (low+height)/2; //中间索引
        int halfVal = source[halfIndex];    //中间索引对应的数字
        if(target==halfVal){    //发现目标
            return halfIndex;
        }else if(target>halfVal){   //如果target大于中间的数字，更新低位索引=中间索引+1
            low=halfIndex+1;
        }else{
            height=halfIndex-1;
        }
    }while (low<=height);

    throw new RuntimeException(target+"不存在");
}
探讨
时间复杂度
二分查找与线性查找相比，时效方面有着明显的优势。
二分查找每次都将查找数据集缩小1/2，那问个问题——在n个数中查找，利用折半算法每次都能将数据集减半（除2），多少次能得到结果（将数据集缩小到2以内）？这个问题再抽象一下：整数n除以多少次数字2，能得到1或0？再换一种问法问：多少个2相乘，能够大于等于（正）整数n？
如果没有把高中数学知识还给物理老师的话，你应该多多少少闻到了些对数的味道！
Tips:
    你可能不记得对数了，但很可能记得什么是幂。"2³=?"就是一个幂运算，显然2³=8。
    那么多少个2相乘是8？这就是对数运算，可以简单记作"log8=？"。对数运算是幂运算的逆运算。
如果还想加深有关对数的理解，可以看下这篇文章——如何理解对数？
说了这么多，其实是在推导这个结论：二分查找的时间复杂度是O(log n)。
劣势
二分法快则快矣，但是有个很大的限制，只能用于有序集合的查找。如果本身是一个无序的集合，只能先排序再强行二分。
其它
还有就是，java已经为我们实现了二分查找，详见Collections.binarySearch。

云服务器 GPU云服务器 php排序和查找二分查找二分查找代码二分法查找

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68853.html

【算】快速排序

摘要：分治快速排序以下简称快排的核心思想是分治法。第二个元素大于，放于右侧第三个元素小于，放于左侧以此类推，最后一个元素放置完毕后是这样的重复。此时从左到右读出图中曾作为基准值的元素菱形，我们发现已经排序好了。分治快速排序（以下简称快排）的核心思想是分治法。可以说，分治提供了另一种解决问题的思路。举个例子来进行说明，抓稳扶好，直接开车了…… 举例现有一个集合{4,8,2,5,7,-1,...

godiscoder 2019-08-15 14:51 评论0 收藏0
数据结构与算法：二分查找

摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。常见数据结构简单数据结构（必须理解和掌握）有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小）无序数据结构：集合、字典、散列表，无序...

zsirfs 2019-08-23 15:33 评论0 收藏0
数据结构与算法：二分查找

摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。常见数据结构简单数据结构（必须理解和掌握）有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小）无序数据结构：集合、字典、散列表，无序...

you_De 2019-08-16 15:26 评论0 收藏0
数据结构与算法：二分查找

摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。常见数据结构简单数据结构（必须理解和掌握）有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小）无序数据结构：集合、字典、散列表，无序...

gotham 2019-07-31 10:07 评论0 收藏0
PHP面试：常见查找算法一篇说透

摘要：我们现在来看二分搜索算法的两种变形插值搜索和指数搜索。插值搜索是对二分搜索算法的改进，插值搜索可以基于搜索的值选择到达不同的位置。预警在本篇文章中，将为各位老铁介绍不同的搜索算法以及它们的复杂度。因为力求通俗易懂，所以篇幅可能较长，大伙可以先Mark下来，每天抽时间看一点理解一点。本文配套的Github Repo，欢迎各位老铁star，会一直更新的。开篇和排序类似，搜索或者叫做...

付永刚 2019-07-01 10:47 评论0 收藏0