現(xiàn)在有一個無序數(shù)組，需要把數(shù)組里面的數(shù)字按照從小到大的順序排列，我們可以怎么做?

比較簡單的一個方法是挨個去查看數(shù)組里面的數(shù)字，找到最小的一個數(shù)字，然后把找到的這個最小數(shù)字放進(jìn)一個新數(shù)組，接下來再去找原先數(shù)組里面剩下的數(shù)字中最小的數(shù)字，找到后再放入新數(shù)組的末尾，這樣一直操作到數(shù)組中的數(shù)字被找完為止。

這種方法就是選擇排序，不斷選擇最小的數(shù)，然后進(jìn)行排序。

def find_smallest(arr):
    smallest = arr[0]
    index = 0
    for i in range(1, len(arr)):
        if smallest > arr[i]:
            smallest = arr[i]
            index = i
    return index


def selection_sort(arr):
    new_arr = []
    for _ in range(len(arr)):
        smallest_index = find_smallest(arr)
        new_arr.append(arr.pop(smallest_index))
    return new_arr

print(selection_sort([4, 1, 5, 3, 2, 8, 7, 6, 9]))

>>>
[1, 2, 3, 4, 5, 6, 7, 8, 9]

如果現(xiàn)在需要去一棵樹的頂端摘一個果子，一般是先爬到第一個樹干，然后再去第二個樹干，一直到樹的頂端，摘到果子后，還要從最靠近頂端的一個樹干，一個一個爬下來，遞歸和這個有點(diǎn)兒像。遞歸中有兩個條件，決定了這個遞歸是可執(zhí)行的，第一個是基線條件，在這里就是能夠在樹上摘到果子，第二個是遞歸條件，這里就是可以到達(dá)下一個樹干。這里還有一個棧的概念，就類似于爬的樹干，一個個爬上去，最后還得一個個爬下來。但是不一樣的是，棧的數(shù)據(jù)是一個個從壓進(jìn)去，然后從頂部一個個拿出來。

一個比較簡單的例子就是用遞歸來計算階乘，

def fact(x):
    if x == 1:
        return 1
    else:
        return x * fact(x-1)
print(fact(5))

>>>
120

可以看出，在計算過程中，把先計算出來的數(shù)放在一邊，直到最后達(dá)到基線條件時在一個個取出來繼續(xù)運(yùn)算。