想象一下，你手里有一張紙，上面列著1000個名字，你需要找到其中一個，但這份名單并非按字母順序排列。這將非常令人沮喪，不是嗎？雖然整理這份名單需要很長時間，但它能使查找名字變得容易得多。因此，將事物排序是我們?nèi)祟惖淖匀辉竿?，搜索已排序的列表顯然比搜索無序列表更省力。

在計算機世界中，需要搜索的列表可能非常龐大，即使是速度很快的計算機，性能也可能會受到影響。在這種情況下，合適的排序和搜索算法將是解決此類問題的方案。排序是將值列表按順序排列的過程，而搜索是在列表中查找值位置的過程。

為了說明這個問題的重要性，讓我向您展示偉大的美國計算機科學(xué)家唐納德·克努斯（Donald Knuth）所說的內(nèi)容：

20世紀(jì)60年代的計算機制造商估計，考慮到所有客戶，他們的計算機運行時間的25%以上都花在了排序上。事實上，在許多安裝案例中，排序任務(wù)占用了超過一半的計算時間。從這些統(tǒng)計數(shù)據(jù)中，我們可以得出結(jié)論：（i）排序有許多重要的應(yīng)用，或者（ii）許多人在不應(yīng)該排序的時候進(jìn)行排序，或者（iii）低效的排序算法已被普遍使用?！队嬎銠C程序設(shè)計藝術(shù)》第3卷：排序和搜索，第3頁

在本教程中，我將向您展示如何實現(xiàn)選擇排序算法和線性搜索算法。

但在我們開始之前，如果您只想在Python代碼中進(jìn)行排序和搜索，我將向您展示內(nèi)置的方法。

Python中的內(nèi)置排序方法和函數(shù)

您可以使用Python創(chuàng)建許多排序算法。這是一個很好的學(xué)習(xí)練習(xí)，但對于生產(chǎn)應(yīng)用程序，您應(yīng)該堅持使用Python中的內(nèi)置存儲函數(shù)和方法。

Python有一個list.sort()方法，您可以使用它來就地排序列表。Python幕后使用的排序算法稱為Timsort。它是一種基于插入排序和合并排序的混合排序算法，在許多現(xiàn)實生活中都能提供出色的性能。以下是如何使用這兩個函數(shù)和方法的示例：

marks_a = [61, 74, 58, 49, 95, 88]
marks_b = [94, 85, 16, 47, 88, 59]

# [49, 58, 61, 74, 88, 95]
print(sorted(marks_a))

# None
print(marks_b.sort())

# [61, 74, 58, 49, 95, 88]
print(marks_a)

# [16, 47, 59, 85, 88, 94]
print(marks_b)

您可能會注意到上述代碼中的一些情況。sorted()函數(shù)返回一個新的已排序列表，而不會更改原始列表marks_a。但是，原始列表保持不變。另一方面，當(dāng)我們在marks_b上調(diào)用sort()方法時，它返回None。

您可以傳遞一些參數(shù)來修改排序行為。例如，將一個函數(shù)傳遞給reverse參數(shù)，sorted()函數(shù)在沒有任何參數(shù)的情況下按字母順序?qū)ξ覀兊膯卧~列表進(jìn)行排序。在第二種情況下，我們使用reverse=True來反轉(zhuǎn)已排序單詞的順序。

選擇排序算法

選擇排序算法基于最小值或最大值的連續(xù)選擇。假設(shè)我們有一個列表，我們希望按升序（從小到大）對其進(jìn)行排序。最小的元素將位于列表的開頭，最大的元素將位于列表的結(jié)尾。

假設(shè)原始列表如下所示：

| 7 | 5 | 3.5 | 4 | 3.1 |

我們首先要做的是找到列表中的最小值，在本例中是3.1。

找到最小值后，將該最小值與列表中的第一個元素交換。也就是說，將3.1與7交換。列表現(xiàn)在將如下所示：

| 3.1 | 5 | 3.5 | 4 | 7 |

現(xiàn)在我們確定第一個元素在列表中的正確位置，我們從列表的第二個元素開始重復(fù)上述步驟（查找最小值）。我們可以發(fā)現(xiàn)列表中（從第二個元素開始）的最小值是3.5。因此，我們現(xiàn)在將3.5與5交換。列表現(xiàn)在變?yōu)椋?/p>

| 3.1 | 3.5 | 5 | 4 | 7 |

此時，我們確定第一個元素和第二個元素都在其正確的位置。

現(xiàn)在，我們檢查列表其余部分中的最小值，即從第三個元素5開始。列表其余部分中的最小值是4，我們現(xiàn)在將其與5交換。因此，列表變?yōu)椋?/p>

| 3.1 | 3.5 | 4 | 5 | 7 |

因此，我們現(xiàn)在確定前三個元素位于正確的位置，并且該過程以此方式繼續(xù)。

讓我們看看如何在Python中實現(xiàn)選擇排序算法（基于Isai Damier）：

marks_a = [61, 74, 58, 49, 95, 88]
marks_b = [94, 85, 16, 47, 88, 59]

# [49, 58, 61, 74, 88, 95]
print(sorted(marks_a))

# None
print(marks_b.sort())

# [61, 74, 58, 49, 95, 88]
print(marks_a)

# [16, 47, 59, 85, 88, 94]
print(marks_b)

讓我們通過在上述腳本的末尾添加以下語句來測試該算法：

def selectionSort(aList):
    for i in range(len(aList)):
        least = i
        for k in range(i+1, len(aList)):
            if aList[k] < aList[least]:
                least = k

        swap(aList, least, i)

def swap(A, x, y):
    temp = A[x]
    A[x] = A[y]
    A[y] = temp

在這種情況下，您應(yīng)該得到以下輸出：

[4.6, 4.7, 5.76, 7.3, 7.6, 25.3, 32.4, 43.5, 52.3, 55.3, 86.7]

線性搜索算法

線性搜索算法是一個簡單的算法，其中檢查列表中的每個項目（從第一個項目開始），直到找到所需的項目或到達(dá)列表的末尾。

線性搜索算法在Python中的實現(xiàn)如下（基于Python School）：

my_list = [5.76,4.7,25.3,4.6,32.4,55.3,52.3,7.6,7.3,86.7,43.5]
selectionSort(my_list)
print(my_list)

讓我們測試代碼。在上面的Python腳本的末尾輸入以下語句：

def linearSearch(item,my_list):
    found = False
    position = 0
    while position < len(my_list) and not found:
        if my_list[position] == item:
            found = True
        position = position + 1
    return found

輸入input時，確保它位于單引號或雙引號之間（即'pencil'）。例如，如果您輸入'pencil'，則應(yīng)該得到以下輸出：

Yes, the item is in the bag

而如果您輸入'ruler'作為輸入，則將得到以下輸出：

Oops, your item seems not to be in the bag

結(jié)論

正如我們所看到的，Python再次證明自己是一種易于編程算法概念的編程語言，就像我們在這里處理排序和搜索算法一樣。

需要注意的是，還有其他類型的排序和搜索算法。如果您想使用Python更深入地研究這些算法，可以參考免費的Python面向?qū)ο缶幊探滩摹?/p>

以上是在Python中進(jìn)行分類和搜索的詳細(xì)內(nèi)容。更多信息請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！