包含python查找演算法的實現的詞條

本文目錄一覽：

• 1、python實現折半查找和歸併排序演算法
• 2、python 二分查找演算法函數bi_search(),該函數實現檢索任意一個整數在 prime() 函數生成的
• 3、python快速查找演算法應用實例
• 4、python實現二分查找演算法

python實現折半查找和歸併排序演算法

python實現折半查找和歸併排序演算法

今天依舊是學演算法，前幾天在搞bbs項目，界面也很醜，評論功能好像也有BUG。現在不搞了，得學下演算法和數據結構，筆試過不了，連面試的機會都沒有……

今天學了折半查找演算法，折半查找是蠻簡單的，但是歸併排序我就挺懵比，看教材C語言寫的歸併排序看不懂，後來參考了別人的博客，終於搞懂了。

折半查找

先看下課本對於 折半查找的講解。注意了，折半查找是對於有序序列而言的。每次折半，則查找區間大約縮小一半。low,high分別為查找區間的第一個下標與最後一個下標。出現lowhigh時，說明目標關鍵字在整個有序序列中不存在，查找失敗。

看我用python編程實現:

defBinSearch(array, key, low, high): mid=int((low+high)/2) ifkey==array[mid]:# 若找到 returnarray[mid] iflow high: returnFalse ifkey array[mid]: returnBinSearch(array, key, low, mid-1)#遞歸 ifkey array[mid]: returnBinSearch(array, key, mid+1, high) if__name__==”__main__”: array=[4,13,27,38,49,49,55,65,76,97] ret=BinSearch(array,76,0,len(array)-1)# 通過折半查找，找到65 print(ret)

輸出: 在列表中查找76.

76

時間複雜度：O(logn)

歸併排序演算法

先闡述一下排序思路：

首先歸併排序使用了二分法，歸根到底的思想還是分而治之。歸併排序是指把無序的待排序序列分解成若干個有序子序列，並把有序子序列合併為整體有序序列的過程。長度為1的序列是有序的。因此當分解得到的子序列長度大於1時，應繼續分解，直到長度為1.

(下圖是分解過程，圖自python編程實現歸併排序)

合併的過程如下:

很好，你現在可以和別人說，老子會歸併排序了。但是讓你寫代碼出來，相信你是不會的……

來來來，看我用python寫的歸併排序演算法:

defmerge_sort(array):# 遞歸分解 mid=int((len(array)+1)/2) iflen(array)==1:# 遞歸結束的條件，分解到列表只有一個數據時結束 returnarray list_left=merge_sort(array[:mid]) list_right=merge_sort(array[mid:]) print(“list_left:”, list_left) print(“list_right:”, list_right) returnmerge(list_left, list_right)# 進行歸併 defmerge(list_left, list_right):# 進行歸併 final=[] whilelist_leftandlist_right: iflist_left[0] =list_right[0]:# 如果將”=”改為””,則歸併排序不穩定 final.append(list_left.pop(0)) else: final.append(list_right.pop(0)) returnfinal+list_left+list_right# 返回排序好的列表 if__name__==”__main__”: array=[49,38,65,97,76] print(merge_sort(array))輸出:

輸出：

list_left: [49]

list_right: [38]

list_left: [38, 49]

list_right: [65]

list_left: [97]

list_right: [76]

list_left: [38, 49, 65]

list_right: [76, 97]

[38, 49, 65, 76, 97]

時間度雜度: 平均情況＝最好情況＝最壞情況＝O(nlogn)

空間複雜度:O(n)

穩定性:穩定

對序列{ 6, 5, 3, 1, 8, 7, 2, 4 }進行歸併排序的實例如下:

使用歸併排序為一列數字進行排序的宏觀過程:

以上就是本文的全部內容，希望對大家的學習有所幫助

python 二分查找演算法函數bi_search(),該函數實現檢索任意一個整數在 prime() 函數生成的

def prime(n):

    if n=2:

        return []

    result=[False,False]+[True]*(n-2)

    for i in range(len(result)):

        if result[i]==True:

            for j in range(2*i,len(result),i):

                result[j]=False

    return [i for i in range(len(result)) if result[i]==True]

def bi_search(prime,primelist,start,end):

    if startend :

        return -1

    mid=(start+end)//2

    if primelist[mid]==prime:

        return mid

    elif primelist[mid]prime:                

        end=mid-1

    else:

        start=mid+1

    return bi_search(prime,primelist,start,end)

if __name__==’__main__’:

    n=int(raw_input())

    primelist=prime(n)

    num=raw_input()

    while num:

        num=int(num)

        index=bi_search(num,primelist,0,len(primelist)-1)

        print(index)

        num=raw_input()

python快速查找演算法應用實例

python快速查找演算法應用實例

文實例講述了Python快速查找演算法的應用，分享給大家供大家參考。

具體實現方法如下：

import random

def partition(list_object,start,end):

random_choice = start

#random.choice(range(start,end+1))

#把這裡的start改成random()效率會更高些

x = list_object[random_choice]

i = start

j = end

while True:

while list_object[i] x and i end:

i += 1

while list_object[j] x:

j -= 1

if i = j:

break

list_object[i],list_object[j] = list_object[j],list_object[i]

print list_object

#list_object[random_choice] = list_object[j]

#list_object[j] = random_choice

return j

def quick_sort(list_object,start,end):

if start end:

temp = partition(list_object,start,end)

quick_sort(list_object,start,temp-1)

quick_sort(list_object,temp + 1 ,end)

a_list = [69,65,90,37,92,6,28,54]

quick_sort(a_list,0,7)

print a_list

程序測試環境為Python2.7.6

輸出結果如下：

[54, 65, 28, 37, 6, 69, 92, 90]

[6, 37, 28, 54, 65, 69, 92, 90]

[6, 37, 28, 54, 65, 69, 92, 90]

[6, 28, 37, 54, 65, 69, 92, 90]

[6, 28, 37, 54, 65, 69, 90, 92]

[6, 28, 37, 54, 65, 69, 90, 92]

希望本文所述對大家的Python程序設計有所幫助。

python實現二分查找演算法

二分查找演算法，是常見的搜索演算法之一，適用於有序的序列，通過將序列不斷的對摺分為區間，從而確定查找值是否存在，優點是速度快。

首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。重複以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

使用python遞歸實現其演算法：

二分查找是應用在數據量較大的場景中，如一些圖片的RGB數組操作中，典型的是在滑塊驗證中使用二分法來確定最佳距離。