Die Bucket-Sortierung ist eine generische Variante des Klassifizierungsalgorithmus, der auf der Basis willkürlicher Grenzen eine Liste in "Buckets" aufteilt, die Buckets sortiert und die Buckets der Reihe nach neu kombiniert.
Sei A1,A2,...,An reelle Zahlen zwischen [0,2k] (k ist konstant). Es ist bekannt, dass für jedes Paar von Ai,AJ dann |Ai-Aj|>=k/n ,
Beschreiben Sie einen Algorithmus, der die Zahlen in O(n) runtime worst-case sortiert.
Ich...