sehr sehr mäßige Sortierung - Java, Arrays, Algorithmus, Sortierung

Angenommen, wir haben ein Array (int [] m).

Ich muss es sortieren ... Ergebnis muss sein:

Alle Elemente in der ersten Hälfte müssen kleiner oder gleich sein als alle Elemente in der zweiten Hälfte.

wie es geht?...

Antworten:

Wie Karl bereits in seinem Kommentar erwähnt hat, ist die Aufgabe gleich a Abschiedsschritt in dem Quicksort-Algorithmus mit Ausnahme dass Sie zuerst den Beispielmedian finden und ihn als Pivot-Element verwenden müssen.

Computing a Median Kann mit O (n) -Operationen berechnet werden, ist der Partitionierungsschritt ebenfalls linear (O (n)), sodass die Leistung im ungünstigsten Fall insgesamt immer noch besser ist als bei einer vollständigen Sortierung (O (n log (n)).

Der Algorithmus sieht folgendermaßen aus (Standardmethoden müssen implementiert werden):

public int[] roughSort(int[] input) {
int pivot = findMedian(input);
int[] result = partition(input, pivot);
return result;
}

   Arrays.sort(array);
for (int i : array) {
System.out.println(i);
}

Das Sortieren in aufsteigender Reihenfolge ist für Ihren Fall in Ordnung.

List<Integer> list = new ArrayList<Integer>();

list.add(2);
list.add(5);
list.add(1);
list.add(15);
list.add(55);
list.add(23);

Collections.sort(list);

int length = list.size();

List<Integer> list1 = list.subList(0, length/2);
List<Integer> list2 = list.subList(length/2, length);

Collections.shuffle(list1);
Collections.shuffle(list2);

List<Integer> newList = new ArrayList<Integer>();
newList.addAll(list1);
newList.addAll(list2);

System.out.println(newList);

Wolltest du das?