Wie sortiere ich eine Liste mit gegebenem Bereich in O (n) - Algorithmus, Sortierung

Wenn ich eine Liste mit der Größe n habe und weiß, dass die Zahlen in der Liste zwischen 1 und 2n liegen, wie würde ich es lösen, wenn der schlechteste Fall O (n) wäre?

Ich dachte, wenn es zwischen 1 und n wäre, könnte ich einfach die Zahl nehmen und sie mit dem Wert des Arrays bei dieser Zahl austauschen - 1, aber dann würde es nicht sortieren, wenn es ein Duplikat gäbe.

Ich dachte an einen ähnlichen Ansatz für die Liste mit einer Nummer zwischen 1 und 2n, aber ich kann es anscheinend nicht herausfinden. Irgendwelche Hilfe bitte?

Antworten:

4 für die Antwort № 1

Normalerweise benötigen Sie eine nicht vergleichende Sortierungin O (n) Zeit sortieren, aber das ist, wenn Sie bereits bestimmte Informationen erhalten haben. Es gibt drei "Haupt" -Sortieralgorithmen, die nicht verglichen werden können: z. B. sort, radix sort und bucket sort.

Verwenden Sie zählende Sortierung, wenn Sie wissen, dass die Eingabe istkleine ganze Zahlen. Laut Wikipedia ist "das Zählen von Sortierungen nur für Situationen geeignet, in denen die Variation der Schlüssel nicht wesentlich größer ist als die Anzahl der Elemente." http://en.wikipedia.org/wiki/Counting_sort

Sie können die Radix-Sortierung verwenden, wenn alle Zahlen, die Sie sortieren, die gleiche Anzahl von ganzen Zahlen haben. Bsp .: 211, 311, 122.

Bucket-Sortierung scheint die beste Option für Sie zu sein. Ihr Ansatz klingt gut, aber Sie brauchen kein Array von 1 bis 2n mit einem Index für jede Zahl. In bucket sort können Sie ein Array von 1 bis 20 haben und in jedem Element eine verknüpfte Liste haben. Wenn Sie also die Zahl 109 setzen, könnte sie dem Index 10 entsprechen.

---

6 für die Antwort № 2

Zählen Sortieren kann operieren Auf) in Ihrem Fall. Sehen Sie sich die Definition von Wikipedia an

Zählsortierung ist ein Algorithmus zum Sortieren von aSammlung von Objekten nach Schlüsseln, die kleine ganze Zahlen sind; Das heißt, es ist eine ganze Zahl Sortieralgorithmus. Es funktioniert durch Zählen der Anzahl der Objekte, die habe jeden einzelnen Schlüsselwert und benutze Arithmetik für diese Anzahl an Bestimmen Sie die Positionen jedes Schlüsselwerts in der Ausgabesequenz. Es ist Laufzeit ist linear in der Anzahl der Elemente und der Unterschied zwischen den maximalen und minimalen Schlüsselwerten, so ist es nur für direkte Verwendung in Situationen, in denen die Variation der Schlüssel nicht gegeben ist deutlich größer als die Anzahl der Artikel

http://en.wikipedia.org/wiki/Counting_sort

---

0 für die Antwort № 3

Sie können die Radix-Sortierung hier verwenden. Wenn Sie eine Beschränkung für die Eingabe haben, wie in Ihrem Fall, funktioniert es gut. Schau dir den Algorithmus hier an - http://en.wikipedia.org/wiki/Radix_sort

---

0 für die Antwort № 4

Sie können radix sort verwenden, zähle sort, es gibt viele O (n) -Sorten.

Aber die Frage macht es Ihnen wirklich leicht ...

In Java:

int [n] input = {your list of n numbers}; int [2*n] listinorder; int [n] output;

for (int i=0, i<2n, i++) listinorder[i] = -1; // set all values of listinorder to -1

for (int i=0, i < n, i++) listinorder[input[i]] = input[i]; // set the ith value of listinorder to i

int j=0;

for (int i=0, i<2n, i++) if (listinorder(i)  != -1) {output[j] = i; j++};

Auf Englisch:

1. Richten Sie ein Array (etwa listinorder) der Länge 2n ein.
2. Setzen Sie jeden Wert auf -1. Blättern Sie durch die Eingabeliste.
3. Setzen Sie für jeden Wert i in der Eingabeliste den entsprechenden Wert von listinorder zu i (dh listinorder[i]=i). Dann schreite durch die Werte der Listinordnung, die "t -1" sind, um die sortierte Liste zu erzeugen.

Alles O (n).

---