成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

【算】選擇排序和二分查找

endless_road / 2740人閱讀

摘要：劣勢二分法快則快矣，但是有個(gè)很大的限制，只能用于有序集合的查找。如果本身是一個(gè)無序的集合，只能先排序再強(qiáng)行二分。其它還有就是，已經(jīng)為我們實(shí)現(xiàn)了二分查找，詳見。

序

大概半個(gè)月前，偶爾看到《算法圖解》，沒翻幾頁便被數(shù)學(xué)戰(zhàn)五渣的我奉為神書，怎一個(gè)相見恨晚、愛不釋手加老淚縱橫??！遂寫文以作積累……

選擇排序 思路

選擇排序的思路很好理解，以從小到大排序?yàn)槔?/p>

選出集合中最小的元素，置于目標(biāo)集合第一個(gè)位置

重復(fù)上述過程，剩余元素中選出最小的元素，置于目標(biāo)集合第二個(gè)位置……以此類推，直到最后一個(gè)元素.

代碼示例

PositionBean類

示例將對int[]進(jìn)行排序，為了方便處理 int[] 數(shù)組 中的索引信息，構(gòu)建了PositionBean類。（后續(xù)的探討其它算法的文章中，也多以int[]為例，同樣會用到PositionBean）

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

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

算法實(shí)現(xiàn)

查找最小值方法

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

    return new PositionBean(min,minIndex);
}

選擇排序?qū)崿F(xiàn)

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

移除數(shù)組指定元素的方法


/**
 * 移除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



代碼很簡單，不多做解釋。

二分查找
思路

大家以前玩沒玩過猜數(shù)游戲？一個(gè)人（張三）先寫下1到100的數(shù)字中任意一個(gè)數(shù)，另一個(gè)人（李四）去猜，張三根據(jù)對方的猜測情況提示“大了”、“小了”，直到猜對！


線性


李四可以選擇從1開始猜，接下來的劇情會是這樣的：


李：1
張：小了
李：2
張：小
……


這種猜法，最多猜100次。也就是說，最壞情況做了集合遍歷，時(shí)間復(fù)雜度記作O(n)


折半


當(dāng)然李四也有另外的選擇：


李：50
張：小了
李：25
張：大了
……


小李子每次都選擇了中間的數(shù)字進(jìn)行猜，而通過張三的提示，每次都能排除當(dāng)前集合近半的不符合條件的數(shù)字：將當(dāng)前集合（1~100）以 中間數(shù)字 進(jìn)行分隔，要么在數(shù)字較小的結(jié)合中（1~50），要么在數(shù)字較大的集合中（51~100）。


這種方式，就是我們要探討的二分查找，也叫折半查找。給出示意圖：




第一次比較后，由于目標(biāo)值大于中間數(shù)（target=10 > 中間數(shù)=8），因此中間數(shù)左側(cè)（含中間數(shù)）數(shù)字-1,1,5,8已然出局（圖中第二次比較，將出局的數(shù)字格畫成了虛線）

代碼示例

依照上面的示意圖寫出代碼：


/**
 * 在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];    //中間索引對應(yīng)的數(shù)字
        if(target==halfVal){    //發(fā)現(xiàn)目標(biāo)
            return halfIndex;
        }else if(target>halfVal){   //如果target大于中間的數(shù)字，更新低位索引=中間索引+1
            low=halfIndex+1;
        }else{
            height=halfIndex-1;
        }
    }while (low<=height);

    throw new RuntimeException(target+"不存在");
}

探討

時(shí)間復(fù)雜度


二分查找與線性查找相比，時(shí)效方面有著明顯的優(yōu)勢。
二分查找每次都將查找數(shù)據(jù)集縮小1/2，那問個(gè)問題——在n個(gè)數(shù)中查找，利用折半算法每次都能將數(shù)據(jù)集減半（除2），多少次能得到結(jié)果（將數(shù)據(jù)集縮小到2以內(nèi)）？這個(gè)問題再抽象一下：整數(shù)n除以多少次數(shù)字2，能得到1或0？再換一種問法問：多少個(gè)2相乘，能夠大于等于（正）整數(shù)n？


如果沒有把高中數(shù)學(xué)知識還給物理老師的話，你應(yīng)該多多少少聞到了些對數(shù)的味道！


Tips:
    你可能不記得對數(shù)了，但很可能記得什么是冪。"23=?"就是一個(gè)冪運(yùn)算，顯然23=8。
    那么多少個(gè)2相乘是8？這就是對數(shù)運(yùn)算，可以簡單記作"log8=？"。對數(shù)運(yùn)算是冪運(yùn)算的逆運(yùn)算。


如果還想加深有關(guān)對數(shù)的理解，可以看下這篇文章——如何理解對數(shù)？


說了這么多，其實(shí)是在推導(dǎo)這個(gè)結(jié)論：二分查找的時(shí)間復(fù)雜度是O(log n)。


劣勢


二分法快則快矣，但是有個(gè)很大的限制，只能用于有序集合的查找。如果本身是一個(gè)無序的集合，只能先排序再強(qiáng)行二分。


其它


還有就是，java已經(jīng)為我們實(shí)現(xiàn)了二分查找，詳見Collections.binarySearch。

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/68853.html

相關(guān)文章

  • 【算】快速排序

    摘要：分治快速排序以下簡稱快排的核心思想是分治法。第二個(gè)元素大于，放于右側(cè)第三個(gè)元素小于，放于左側(cè)以此類推，最后一個(gè)元素放置完畢后是這樣的重復(fù)。此時(shí)從左到右讀出圖中曾作為基準(zhǔn)值的元素菱形，我們發(fā)現(xiàn)已經(jīng)排序好了。 分治 快速排序（以下簡稱快排）的核心思想是分治法。可以說，分治提供了另一種解決問題的思路。舉個(gè)例子來進(jìn)行說明，抓穩(wěn)扶好，直接開車了…… 舉例 現(xiàn)有一個(gè)集合{4,8,2,5,7,-1,...

    godiscoder 評論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法：二分查找

    摘要：為檢查長度為的列表，二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹關(guān)于二叉樹，戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹算法常見練習(xí)在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。 常見數(shù)據(jù)結(jié)構(gòu) 簡單數(shù)據(jù)結(jié)構(gòu)（必須理解和掌握） 有序數(shù)據(jù)結(jié)構(gòu)：棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間（儲存空間?。?無序數(shù)據(jù)結(jié)構(gòu)：集合、字典、散列表，無序...

    zsirfs 評論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法：二分查找

    摘要：為檢查長度為的列表，二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹關(guān)于二叉樹，戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹算法常見練習(xí)在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。 常見數(shù)據(jù)結(jié)構(gòu) 簡單數(shù)據(jù)結(jié)構(gòu)（必須理解和掌握） 有序數(shù)據(jù)結(jié)構(gòu)：棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間（儲存空間?。?無序數(shù)據(jù)結(jié)構(gòu)：集合、字典、散列表，無序...

    you_De 評論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法：二分查找

    摘要：為檢查長度為的列表，二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹關(guān)于二叉樹，戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹算法常見練習(xí)在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。 常見數(shù)據(jù)結(jié)構(gòu) 簡單數(shù)據(jù)結(jié)構(gòu)（必須理解和掌握） 有序數(shù)據(jù)結(jié)構(gòu)：棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間（儲存空間?。?無序數(shù)據(jù)結(jié)構(gòu)：集合、字典、散列表，無序...

    gotham 評論0 收藏0

  • PHP面試：常見查找算法一篇說透

    摘要：我們現(xiàn)在來看二分搜索算法的兩種變形插值搜索和指數(shù)搜索。插值搜索是對二分搜索算法的改進(jìn)，插值搜索可以基于搜索的值選擇到達(dá)不同的位置。 預(yù)警 在本篇文章中，將為各位老鐵介紹不同的搜索算法以及它們的復(fù)雜度。因?yàn)榱η笸ㄋ滓锥?，所以篇幅可能較長，大伙可以先Mark下來，每天抽時(shí)間看一點(diǎn)理解一點(diǎn)。本文配套的Github Repo，歡迎各位老鐵star，會一直更新的。 開篇 和排序類似，搜索或者叫做...

    付永剛 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<