Warum können Sie keine Hash -Tabellen/-wörterbücher verwenden, um den Sort -Algorithmus zu zählen? ⇐ Python

[Anonymous]

Wenn Sie den Zähls -Sort -Algorithmus verwenden, erstellen Sie eine Liste und verwenden ihre Indizes als Schlüssel, während die Anzahl der Ganzzahl -Vorkommen als Werte in der Liste hinzugefügt wird. Warum ist dies nicht dasselbe wie einfach ein Wörterbuch mit den Schlüssel als Index und die Zählungen als Werte? Wie: < /p>

Code: Select all

hash_table = collections.Counter(numList)
< /code>

oder < /p>

hash_table = {x:numList.count(x) for x in numList}
< /code>

Sobald Sie Ihre Hash -Tabelle erstellt haben, kopieren Sie im Wesentlichen nur die Anzahl der Ganzzahl -Vorkommen in eine andere Liste. Hash -Tabellen/Wörterbücher haben O (1) Suchzeiten. Warum sollte dies also nicht vorzuziehen sein, wenn Sie einfach auf die Schlüssel-/Wertpaare Bezug nehmen?  < /p>

Ich habe den Algorithmus zum Zählen der Sortierung unten als Referenz eingeschlossen: < /p>

def counting_sort(the_list, max_value):
# List of 0's at indices 0...max_value
num_counts = [0] * (max_value + 1)

# Populate num_counts
for item in the_list:
num_counts[item] += 1

# Populate the final sorted list
sorted_list = []

# For each item in num_counts
for item, count in enumerate(num_counts):

# For the number of times the item occurs
for _ in xrange(count):

# Add it to the sorted list
sorted_list.append(item)

return sorted_list