Wie implementiert man einen Zählsortieralgorithmus mit Python?
Counting Sort ist ein linearer Sortieralgorithmus nach Zeitkomplexität, der zum Sortieren von Ganzzahlen oder Arrays mit einem bestimmten Wertebereich verwendet werden kann. Seine Grundidee besteht darin, zu zählen, wie oft jedes Element vorkommt, und das Element basierend auf der Häufigkeit an der richtigen Position zu platzieren. Im Folgenden wird die Verwendung von Python zum Implementieren des Zählsortieralgorithmus vorgestellt und spezifische Codebeispiele gegeben.
Zunächst müssen wir den Kerngedanken der Zählsortierung klären. Die Ausführungsschritte der Zählsortierung lauten wie folgt:
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
Als nächstes können wir den Zählsortieralgorithmus auf folgende Weise testen:
arr = [4, 2, 3, 4, 1] sorted_arr = counting_sort(arr) print(sorted_arr)
Führen Sie den obigen Code aus. Das Ausgabeergebnis lautet: [1 , 2, 3, 4 , 4].
Anhand der obigen Codebeispiele können wir sehen, dass die Implementierungsschritte des Zählsortieralgorithmus relativ einfach sind. Es handelt sich um einen sehr effizienten Sortieralgorithmus für Arrays mit einem bestimmten Wertebereich. Ich hoffe, dieser Artikel hilft Ihnen, den Zählsortieralgorithmus zu verstehen und zu verwenden!
Das obige ist der detaillierte Inhalt vonWie implementiert man einen Zählsortieralgorithmus mit Python?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!