1. Python分治法
    1. 內容

Python分治法

最後更新: 作者: 字数: 252 预计阅读时间: 1min

Python分治法

Python分治法

內容

痾…又來寫筆記了，這次教了quick sort，大致上就是挑選一個值接著把小的放左邊大的放右邊，通常我們拿第一個做挑選然後用遞迴解決這個問題:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
data = [2, 1, 4, 3, 5, 3, 7, 9, 1]
def qs(in_list): #input:1D list output:No, or QS() + (No + QS())
    #print(in_list)
    if len(in_list) <= 1:
        return in_list

    pivot = in_list[0]
    R = []
    L = []
    for No in in_list[1:]:
        if No < pivot:
            R.append(No)
        elif No >= pivot:
            L.append(No)
    #print(R + [pivot] + L)
    return qs(R) + [pivot] + qs(L)

print(qs(data))

接著又教了binary search，大致上就是將一組資料排序後切一半，接著尋找，設最低值和最高值，如果澳尋找得比較小就把最大值縮小，大概是這個概念:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
data = [1, 6, 2, 8, 7, 9]
data.sort()
def binary(data, target):
    L = 0
    R = len(data) - 1
    if L == target:
        return L + 1 
    elif R == target:
        return R + 1
    while L + 1 != R:
        M = (L+R) // 2
        if data[M] == target:
            return M + 1
        elif target < data[M]:
            R = M
        else:
            L = M
print(binary(data, 2))
~~~~