想像一下，你手裡有一張紙，上面列著1000個名字，你需要找到其中一個，但這份名單並非按字母順序排列。這將非常令人沮喪，不是嗎？雖然整理這份名單需要很長時間，但它能使查找名字變得容易得多。因此，將事物排序是我們人類的自然願望，搜索已排序的列表顯然比搜索無序列表更省力。

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

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

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

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

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

Python中的內置排序方法和函數

您可以使用Python創(chuàng)建許多排序算法。這是一個很好的學習練習，但對於生產應用程序，您應該堅持使用Python中的內置存儲函數和方法。

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

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()函數返回一個新的已排序列表，而不會更改原始列表marks_a。但是，原始列表保持不變。另一方面，當我們在marks_b上調用sort()方法時，它返回None。

您可以傳遞一些參數來修改排序行為。例如，將一個函數傳遞給reverse參數，sorted()函數在沒有任何參數的情況下按字母順序對我們的單詞列表進行排序。在第二種情況下，我們使用reverse=True來反轉已排序單詞的順序。

選擇排序算法

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

假設原始列表如下所示：

| 7 | 5 | 3.5 | 4 | 3.1 |

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

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

| 3.1 | 5 | 3.5 | 4 | 7 |

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

| 3.1 | 3.5 | 5 | 4 | 7 |

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

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

| 3.1 | 3.5 | 4 | 5 | 7 |

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

讓我們看看如何在Python中實現選擇排序算法（基於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

在這種情況下，您應該得到以下輸出：

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

線性搜索算法

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

線性搜索算法在Python中的實現如下（基於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'，則應該得到以下輸出：

Yes, the item is in the bag

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

Oops, your item seems not to be in the bag

結論

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

需要注意的是，還有其他類型的排序和搜索算法。如果您想使用Python更深入地研究這些算法，可以參考免費的Python面向對象編程教材。

以上是在Python中進行分類和搜索的詳細內容。更多資訊請關注PHP中文網其他相關文章！