java - manuell - string array sortieren




Übereinstimmende Arrays in Java sortieren (9)

Ein schneller Hack wäre, die beiden Arrays mit Bit-Verschiebungen zu kombinieren. Machen Sie ein Array von Longs so, dass die höchstwertigen 32 Bits die Zahl und die niedrigstwertige 32 die Farbe ist. Verwenden Sie eine Sortiermethode und entpacken Sie diese dann.

Angenommen, ich habe zwei Arrays (in Java),

int [] Zahlen; und int [] Farben;

Jedes i-te Element von Zahlen entspricht seinem i-ten Element in Farben. Ex, Zahlen = {4,2,1} Farben = {0x11, 0x24, 0x01}; Bedeutet, dass Nummer 4 die Farbe 0x11 hat, Nummer 2 0x24 usw.

Ich möchte das Zahlenarray sortieren, aber dann immer noch haben, damit jedes Element mit seinem Paar in Farben übereinstimmt.

Ex. Zahlen = {1,2,4}; Farben = {0x01,0x24,0x11};

Was ist der sauberste und einfachste Weg, dies zu tun? Die Arrays haben ein paar tausend Elemente, also wäre es am besten, aber nicht erforderlich. Wäre es sinnvoll, einen Arrays.sort () und einen benutzerdefinierten Vergleicher zu erstellen? Die Verwendung von Bibliotheksfunktionen ist so weit wie möglich vorzuziehen.

Hinweis: Ich weiß, dass die "beste" Lösung darin besteht, eine Klasse für die beiden Elemente zu erstellen und einen benutzerdefinierten Vergleicher zu verwenden. Diese Frage soll die Leute nach dem schnellsten Weg fragen, dies zu kodieren. Stellen Sie sich vor, Sie wären bei einem Programmierwettbewerb, Sie würden nicht alle diese zusätzlichen Klassen, anonyme Klassen für den Vergleicher usw. erstellen wollen. Noch besser, vergessen Sie Java; Wie würden Sie es in C codieren?


Es scheint so, als wäre das Sauberste, eine benutzerdefinierte Eigenschaftsklasse zu erstellen, die Comparable implementiert. Beispielsweise:

class Color implements Comparable {
  private int number;
  private int color;

  // (snip ctor, setters, etc.)

  public int getNumber() {
    return number;
  }
  public int getColor() {
    return color;
  }

  public int compareTo(Color other) {
    if (this.getNumber() == other.getNumber) {
      return 0;
    } else if (this.getNumber() > other.getNumber) {
      return 1;
    } else {
      return -1;
    }
  }
}

Dann können Sie Ihren Sortieralgorithmus von der Sortierlogik trennen (Sie könnten Collections.sort verwenden, wenn Sie eine Liste anstelle eines Arrays verwenden) und vor allem müssen Sie sich keine Sorgen machen, dass zwei Arrays nicht synchronisiert werden.


Sie müssen das Farbenarray nach seinem relativen Element im Zahlenarray sortieren. Geben Sie einen Vergleicher an, der Zahlen vergleicht und als Vergleich für das Farbenarray verwendet.


Würde es genügen, Ihre eigene Sortiermethode zu codieren? Ein einfacher Bubblesort wäre wahrscheinlich schnell zu kodieren (und richtig zu machen). Keine Notwendigkeit für zusätzliche Klassen oder Komparatoren.


Wenn Sie bereit wären, etwas zusätzlichen Speicherplatz zuzuweisen, könnten Sie ein weiteres Array generieren, das Sie extra nennen könnten, mit Elementen wie diesem:

extra = [0,1,...,numbers.length-1]

Dann könnten Sie dieses zusätzliche Array mit Arrays.sort () mit einem benutzerdefinierten Komparator sortieren (das beim Vergleich der Elemente i und j die Zahlen [extra [i]] und die Zahlen [extra [j]] vergleicht). Auf diese Weise würde extra [0] nach dem Sortieren des zusätzlichen Arrays den Index der kleinsten Zahl und, da sich Zahlen und Farben nicht bewegen, die entsprechende Farbe enthalten.
Das ist nicht sehr nett, aber es erledigt die Arbeit und ich kann mir keinen einfacheren Weg vorstellen.

Nebenbei bemerkt, in der Konkurrenz finde ich normalerweise die C ++ - Vorlagen und schöne Karten unentbehrlich;)


Der einfachste Weg, dies in C zu tun, wäre bubblesort + dual pointers. Am schnellsten wäre natürlich quicksort + two pointers. Natürlich behält der zweite Zeiger die Korrelation zwischen den beiden Arrays bei.

Ich würde lieber Werte definieren, die in zwei Arrays als Struktur gespeichert sind, und die Struktur in einem einzelnen Array verwenden. Dann verwende QuickSort darauf. Sie können eine generische Version von sort schreiben, indem Sie eine Vergleichsfunktion aufrufen, die dann für jede Struktur geschrieben werden kann, aber dann wissen Sie das schon :)



Sie könnten sort () mit einem benutzerdefinierten Komparator verwenden, wenn Sie ein drittes Array mit dem Index beibehalten und dieses sortiert haben, sodass die Daten intakt bleiben.

Java-Codebeispiel:

Integer[] idx = new Integer[numbers.length];
for( int i = 0 ; i < idx.length; i++ ) idx[i] = i;              
Arrays.sort(idx, new Comparator<Integer>() {
    public int compare(Integer i1, Integer i2) {                        
        return Double.compare(numbers[i1], numbers[i2]);
    }                   
});

// numbers[idx[i]] is the sorted number at index i
// colors[idx[i]] is the sorted color at index i

Beachten Sie, dass Sie Integer anstelle von int oder keinen benutzerdefinierten Vergleicher verwenden können.


Ich schätze, dass Sie eine Leistungsoptimierung wünschen, während Sie versuchen, die Verwendung eines Array von Objekten zu vermeiden (was ein schmerzhaftes GC-Ereignis verursachen kann). Leider gibt es keine allgemeine Lösung, dachte ich. Aber für Ihren speziellen Fall, in dem sich die Zahlen voneinander unterscheiden, können nur zwei Felder erstellt werden.

/**
 * work only for array of different numbers
 */
private void sortPairArray(int[] numbers, int[] colors) {
    int[] tmpNumbers = Arrays.copyOf(numbers, numbers.length);
    int[] tmpColors = Arrays.copyOf(colors, colors.length);
    Arrays.sort(numbers);
    for (int i = 0; i < tmpNumbers.length; i++) {
        int number = tmpNumbers[i];
        int index = Arrays.binarySearch(numbers, number); // surely this will be found
        colors[index] = tmpColors[i];
    }
}

Zwei sortierte Arrays können durch Int2IntOpenHashMap ersetzt werden , was eine schnellere Ausführung ermöglicht, aber die Speicherauslastung könnte doppelt so hoch sein.





list