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

endless_road 發布于2019-08-15 14:50 / 2737人閱讀

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

序

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

選擇排序 思路

選擇排序的思路很好理解，以從小到大排序為例：

選出集合中最小的元素，置于目標集合第一個位置

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

代碼示例

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:
    你可能不記得對數了，但很可能記得什么是冪。"23=?"就是一個冪運算，顯然23=8。
    那么多少個2相乘是8？這就是對數運算，可以簡單記作"log8=？"。對數運算是冪運算的逆運算。
如果還想加深有關對數的理解，可以看下這篇文章——如何理解對數？
說了這么多，其實是在推導這個結論：二分查找的時間復雜度是O(log n)。
劣勢
二分法快則快矣，但是有個很大的限制，只能用于有序集合的查找。如果本身是一個無序的集合，只能先排序再強行二分。
其它
還有就是，java已經為我們實現了二分查找，詳見Collections.binarySearch。

云服務器 GPU云服務器 php排序和查找二分查找二分查找代碼二分法查找

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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