Gegeben ein N-Nummernbereich, z.B. [1 bis 100], sortiere die Zahlen in Ziffernfolge (d. H.) Für die Zahlen 1 bis 100 wird die sortierte Ausgabe bewickelt 1 10 100 11 12 13. . . 19 2 20 21 ..... 99
Dies ist genau wie bei Radix Sort, aber nur, dass die Ziffern in umgekehrter Reihenfolge sortiert sind, wie bei einer normalen Radix-Sortierung.
Ich habe versucht, alle Ziffern in jeder Zahl als verkettete Liste für eine schnellere Operation zu speichern, aber es ergibt sich eine große Raumkomplexität.
Ich brauche einen funktionierenden Algorithmus für die Frage.
Von allen Antworten ist "Konvertieren in Strings" eine Option, aber gibt es keine andere Möglichkeit dies zu tun? Es kann auch ein Algorithmus zum Sortieren von Zeichenfolgen wie oben erwähnt angegeben werden.
Verwenden Sie einen beliebigen Sortieralgorithmus, aber vergleichen Sie die Zahlen als Zeichenfolgen , nicht als Zahlen. Dies ist im Grunde lexikografische Sortierung von regulären Zahlen. Hier ist ein Beispiel für eine Gnome-Sortierung in C:
%Vor% Dies erfordert natürlich, dass die nicht standardmäßige Funktion itoa in stdlib.h vorhanden ist. Eine Standard-Alternative wäre die Verwendung von sprintf , aber das macht den Code etwas unübersichtlicher. Sie sollten möglicherweise das ganze Array zuerst in Strings konvertieren, dann sortieren und dann zurück konvertieren.
Bearbeiten: Als Referenz ist hier das relevante Bit strcmp(itoa(*iter, &buf1, 10), itoa(*(iter-1), &buf2, 10) >= 0 , das *iter >= *(iter-1) ersetzt.
Ich habe eine Lösung, aber nicht genau einen Algorithmus. Alles, was Sie tun müssen, ist die Umwandlung aller Zahlen in Strings & amp; sortiere sie als Zeichenfolgen.
Hier ist, wie Sie es mit einer rekursiven Funktion tun können (der Code ist in Java):
%Vor%Sie nennen es so:
%Vor%BEARBEITEN:
Ich habe meinen Code in C ++ hier übersetzt:
%Vor% Grundsätzlich ist die Idee: Für jede Ziffer (0-9) füge ich sie zum Array hinzu, wenn sie zwischen minimum und maximum liegt. Dann rufe ich die gleiche Funktion mit dieser Ziffer als Präfix auf. Es macht das gleiche: Für jede Ziffer fügt es es dem Präfix (% co_de%) hinzu und wenn es zwischen den Grenzen liegt, fügt es es dem Array hinzu. Es stoppt, wenn prefix * 10 + i größer als Maximum ist.
Optimieren Sie die Art und Weise, wie Sie die Zahlen speichern: Verwenden Sie eine binärcodierte Dezimalzahl (BCD) Geben Sie den einfachen Zugriff auf eine bestimmte Ziffer ein. Dann können Sie Ihren aktuellen Algorithmus verwenden, den Steve Jessop korrekt als identifiziert hat höchstwertige Ziffer radix sort .
Ich habe versucht, alle Ziffern zu speichern jede Nummer als eine verknüpfte Liste für schnellere Operation, aber es ergibt sich ein große Raumkomplexität.
Wenn Sie jede Ziffer in einer verknüpften Liste speichern, wird Platz auf zwei verschiedene Arten verschwendet:
char oder short Typ benötigt 8 Bits und ein int kann bis zu 64 Bits benötigen. Das ist 2X bis 16X mehr Speicher als die optimale Lösung! Eine speicherfreundlichere Lösung speichert BCD Ziffern zusammenhängend im Speicher:
Eine Option, wenn andere Operationen wie Addition / Multiplikation nicht wichtig sind, besteht darin, genügend Speicher zuzuweisen, um jede BCD-Ziffer plus einen BCD-Terminator zu speichern. Der BCD-Terminator kann eine beliebige Kombination von 4 Bits sein, die nicht zur Darstellung einer BCD-Ziffer verwendet wird (wie binary 1111 ). Wenn Sie diesen Weg speichern, werden andere Operationen wie Addition und Multiplikation schwieriger.
Beachten Sie, dass dies der Idee ähnelt, in Strings zu konvertieren und diese Strings lexikographisch zu sortieren. Ganzzahlen werden intern als Binärdatei (Basis 2) im Computer gespeichert. Speichern in BCD ist mehr wie Base 10 (Basis 16, tatsächlich, aber 6 Kombinationen werden ignoriert), und Strings sind wie Base 256. Strings werden etwa doppelt so viel Speicher verwenden, aber es gibt bereits effiziente Funktionen zum Sortieren von Strings geschrieben. BCDs müssen wahrscheinlich einen benutzerdefinierten BCD-Typ für Ihre Bedürfnisse entwickeln.
Bearbeiten: Ich habe übersehen, dass es sich um einen zusammenhängenden Bereich handelt. Das ist der Fall, alle Antworten, die über das Sortieren eines Arrays sprechen, sind falsch (einschließlich Ihrer Idee in der Frage, dass es wie eine Radix-Art ist), und die Antwort von True Soft ist richtig.
genau wie Radix Sort, nur dass die Ziffern in umgekehrter Reihenfolge sortiert sind
Gut gepunktet :-) Wenn Sie es tatsächlich so machen, komischerweise wird es eine MSD-Radix-Sortierung genannt.
Sie können einen sehr einfach oder mit viel Spitzentechnologie und Fanfaren implementieren. In den meisten Programmiersprachen hat Ihr spezielles Beispiel eine leichte Schwierigkeit. Das Extrahieren von Dezimalziffern aus dem natürlichen Speicherformat einer ganzen Zahl ist keine besonders schnelle Operation. Sie können dies ignorieren und sehen, wie lange es dauert (empfohlen), oder Sie können noch mehr Fanfaren hinzufügen, indem Sie vor dem Sortieren alle Zahlen in Dezimalzeichen konvertieren.
Natürlich müssen Sie es nicht als Radix-Sortierung implementieren: Sie könnten einen Vergleichssortieralgorithmus mit einem geeigneten Komparator verwenden. Zum Beispiel in C ist das Folgende für die Verwendung mit qsort geeignet (sofern ich es nicht vermasselt habe):
%Vor%Nicht besonders effizient, da es eine Menge von wiederholter Arbeit macht, aber einfach.
Wenn Sie sie nicht in Zeichenfolgen konvertieren möchten, aber genug Platz zum Speichern einer zusätzlichen Kopie der Liste haben, würde ich die größte Potenz von zehn weniger als das Element in der Kopie speichern. Dies ist wahrscheinlich am einfachsten mit einer Schleife zu tun. Rufen Sie nun Ihr ursprüngliches Array x und die Potenzen von zehn y auf.
Sie könnten sie auch direkt berechnen
%Vor%aber ich vermute, dass die Iteration schneller als die Konvertierungen zum und vom Gleitkomma sein kann.
Um die i th und j th Elemente
Was hier gemacht wird, ist, dass wir die kleinere Zahl mit der entsprechenden Zehnerpotenz multiplizieren, damit die zwei Zahlen die gleiche Anzahl an Ziffern haben, und dann vergleichen. Wenn die beiden modifizierten Zahlen gleich sind, vergleichen Sie die Ziffernlängen.
Wenn Sie keinen Platz zum Speichern der y-Arrays haben, können Sie sie bei jedem Vergleich berechnen.
Im Allgemeinen ist es wahrscheinlich besser, die voroptimierten Ziffernumwandlungsroutinen zu verwenden.
Tags und Links algorithm sorting digits radix-sort