如何使用Python實作計數排序演算法？

如何使用Python實作計數排序演算法？

計數排序是一種線性時間複雜度的排序演算法，可以用於排序整數或具有確定取值範圍的陣列。它的基本想法是統計每個元素出現的次數，並根據次數將元素放置到正確的位置。以下將介紹如何使用Python來實作計數排序演算法，並給出具體的程式碼範例。

首先，我們需要明確計數排序的核心思想。計數排序的執行步驟如下：

1. 找出待排序數組中最大的數，並建立一個長度為最大數加1的輔助數組count，用於儲存每個元素出現的次數；
2. 遍歷待排序數組，統計每個元素出現的次數，並儲存在count數組中；
3. 對count數組進行累加操作，得到每個元素的正確位置索引；
4. 建立與待排序數組長度相同的結果數組result;
5. 遍歷待排序數組，根據元素值在count數組中的索引，將元素放置到正確的位置上；
6. 傳回結果陣列result，即排序完成的陣列。

以下是使用Python實作計數排序演算法的程式碼範例：

def counting_sort(arr):
    # 找出最大值
    max_val = max(arr)
    # 创建辅助数组count，并初始化为0
    count = [0] * (max_val + 1)

    # 统计每个元素出现的次数
    for num in arr:
        count[num] += 1

    # 对count数组进行累加操作
    for i in range(1, len(count)):
        count[i] += count[i - 1]

    # 创建结果数组result
    result = [0] * len(arr)

    # 将元素放置到正确的位置上
    for num in arr:
        index = count[num] - 1
        result[index] = num
        count[num] -= 1

    # 返回结果数组
    return result

接下來，我們可以透過以下方式測試計數排序演算法：

arr = [4, 2, 3, 4, 1]
sorted_arr = counting_sort(arr)
print(sorted_arr)

運行以上程式碼，輸出結果為：[1, 2, 3, 4, 4]。

透過以上程式碼範例，我們可以看到計數排序演算法的實作步驟相對簡單，對於具有確定取值範圍的數組，它是一種非常高效的排序演算法。希望這篇文章對你理解和使用計數排序演算法有幫助！

以上是如何使用Python實作計數排序演算法？的詳細內容。更多資訊請關注PHP中文網其他相關文章！