Sortieren ist eine der häufigsten und notwendigsten Operationen in der Programmierung. Es stellt die Anordnung einiger Elemente in einer bestimmten Reihenfolge dar. In diesem Artikel geht es um Standardmethoden zum Sortieren von Arrays in Java.
Kurz zum Sortieren
Sortieren ist also das Ordnen einer Datenmenge. In unserem Fall Arrays. Der Zweck des Sortierens von Arrays oder anderen Datenstrukturen besteht darin, das Auffinden, Bearbeiten oder Analysieren der Daten in der Sammlung zu erleichtern. Programmierer müssen so oft sortieren, dass jede Programmiersprache integrierte Methoden zum Sortieren von Arrays, Listen und anderen geordneten Datenstrukturen enthält. Um solche Methoden zu verwenden, rufen Sie sie auf. Die Bedienung wird so weit wie möglich vereinfacht. Normalerweise sind integrierte Methoden maximal optimiert; In den meisten Fällen ist es eine gute Idee, sie für Ihre Arbeit oder Projekte zu verwenden. Allerdings muss fast jeder Programmierer im Laufe seines Studiums selbst Sortieralgorithmen implementieren. Daher lernen Sie mit diesen perfekten Übungen, das Wesentliche der Programmierung zu verstehen. Darüber hinaus sind bei der Arbeit manchmal nicht standardmäßige Sortiermethoden erforderlich. Es gibt viele Sortieralgorithmen. Sie haben je nach Art oder Größe der Datensätze Stärken und Schwächen. Zu den Standardsortieralgorithmen gehören Blasensortierung, Auswahlsortierung, Einfügungssortierung, Zusammenführungssortierung und Schnellsortierung.
Integrierte Methode zum Sortieren von Arrays in Java: Arrays.sort
Beginnen wir mit dem Einfachsten. Jemand hat für uns bereits eine Methode zum Sortieren von Arrays in Java geschrieben. Diese Methode befindet sich in der Klasse Arrays , genauer gesagt java.util.Arrays . Diese Klasse enthält verschiedene Methoden zum Arbeiten mit Arrays, wie zum Beispiel Sortieren und Suchen. Die Methode Arrays.sort bietet eine praktische Möglichkeit, Arrays in Java zu sortieren, unabhängig davon, ob sie Zeichenfolgen, Ganzzahlen oder andere Elemente enthalten. Es gibt verschiedene Variationen der Arrays.sort -Methode in Java. Hier sind einige häufig verwendete Sortiermethoden aus der Arrays- Klasse:
Arrays.sort(Array) : Verwenden Sie es, um Arrays primitiver Typen oder Objekte in aufsteigender Reihenfolge zu sortieren. Es nutzt die natürliche Reihenfolge der Elemente.
Arrays.sort(Array, fromIndex, toIndex) : Mit dieser überladenen Sortiermethode können Sie nur einen Teil des Arrays sortieren, das durch die Parameter fromIndex und toIndex angegeben wird.
Arrays.sort(Array, comparator) : Dies dient zum Sortieren von Arrays von Objekten mithilfe eines benutzerdefinierten Komparators. Der Komparator definiert die Reihenfolge der Elemente.
Arrays.parallelSort(Array) : Diese Methodenversion sortiert das Array parallel und nutzt mehrere Threads für eine verbesserte Leistung. Dies ist hilfreich beim Sortieren großer Arrays.
Arrays.parallelSort(Array, fromIndex, toIndex) : Diese überladene Version der parallelSort-Methode ermöglicht das Sortieren eines bestimmten Bereichs von Elementen im Array .
Sie ermöglichen Ihnen eine schnelle Anordnung der Elemente basierend auf ihrer natürlichen Reihenfolge oder mithilfe eines benutzerdefinierten Komparators. Lassen Sie uns diese Methode anhand von zwei Beispielen untersuchen, eines davon mit Strings.
Beispiel 1: Strings sortieren
Angenommen, wir haben eine Reihe von Streichinstrumenten: „Violine“, „Viola“, „Cello“ und „Kontrabass“. Wir können die Methode Array.sort verwenden , um sie alphabetisch zu ordnen.
In diesem Programm importieren wir zunächst die Klasse java.util.Arrays , um Zugriff auf die Methode Array.sort zu erhalten . Dann erstellen wir ein String-Array namens „instruments“, das die Namen der Musikinstrumente enthält. Danach rufen wir Arrays.sort(instruments) auf . Diese Methode ruft also ein Array ab und sortiert die Elemente in aufsteigender Reihenfolge basierend auf ihrer natürlichen Reihenfolge (alphabetisch). Schließlich durchlaufen wir das sortierte Array und drucken jedes Instrument aus.
Beispiel 2: Ganzzahlen sortieren
Betrachten wir ein weiteres Beispiel, bei dem wir ein Array von Ganzzahlen in aufsteigender Reihenfolge sortieren.
importjava.util.Arrays;publicclassIntegerSortExample{publicstaticvoidmain(String[] args){int[] numbers ={8,2,7,3,1,5};//sort an array using Arrays.sortArrays.sort(numbers);System.out.println("Sorted Numbers:");for(int number : numbers){System.out.println(number);}}}
Ausgabe:
Sortierte Zahlen: 1 2 3 5 7 8
Hier erstellen wir ein ganzzahliges Array namens Zahlen mit mehreren unsortierten Elementen. Als nächstes rufen wir Arrays.sort(numbers) auf , um ein Array in aufsteigender Reihenfolge zu sortieren. Beachten Sie, dass die Methode Array.sort das ursprüngliche Array direkt ändert. Um das ursprüngliche Array zu behalten , erstellen Sie vor dem Sortieren eine Kopie.
Beispiel 3: absteigende Reihenfolge
Was ist mit der absteigenden Sortierung? Mit Arrays.sort ist das auch ganz einfach . Verwenden Sie einfach einen benutzerdefinierten Komparator. Hier ist ein Beispiel:
importjava.util.Arrays;importjava.util.Comparator;//Arrays.sort with custom comparator examplepublicclassDescendingSortExample{publicstaticvoidmain(String[] args){Integer[] numbers ={8,2,7,3,1,5};//sort an Array using Arrays.sortArrays.sort(numbers,Comparator.reverseOrder());System.out.println("Sorted Numbers (Descending):");for(int number : numbers){System.out.println(number);}}}
Die Ausgabe ist als nächstes:
Sortierte Zahlen (absteigend): 8 7 5 3 2 1
Hier haben wir ein Array von Ganzzahlen mit dem Namen Zahlen. Indem wir Comparator.reverseOrder() als zweites Argument an die Methode Arrays.sort übergeben , geben wir einen benutzerdefinierten Komparator an, der die Elemente in absteigender Reihenfolge sortiert. Die Methode Comparator.reverseOrder() gibt einen Komparator zurück, der die natürliche Reihenfolge der Elemente umkehrt. Beachten Sie, dass wir hier die Integer-Wrapper-Klasse anstelle des primitiven int-Typs verwenden, da die Methode Comparator.reverseOrder() Objekte erfordert. Wenn Sie über ein Array primitiver int-Werte verfügen, müssen Sie diese auch in Integer- Objekte konvertieren, bevor Sie diesen Ansatz verwenden. Mit einem benutzerdefinierten Komparator können Sie Arrays mithilfe der Arrays.sort- Methode in Java ganz einfach in absteigender Reihenfolge sortieren .
Selbstgeschriebene klassische Sortieralgorithmen in Java
Sie haben bereits Aufgaben zur Array- Sortierung gesehen, wenn Sie selbstständig oder an der Universität Informatik studieren. Es gibt viele verschiedene Sortieralgorithmen, einige davon werden wir in diesem Artikel implementieren. Generell gilt: Je einfacher ein Algorithmus zu implementieren ist, desto weniger effizient ist er. Programmierer messen die Effizienz von Algorithmen an der Zeit ihrer Ausführung und dem Speicher, der für Ressourcen aufgewendet wird. Das ist nicht das Thema unseres Artikels, aber wir erwähnen, dass Arrays.sort in Java ein effektiver Algorithmus ist.
Blasensortierung
Beginnen wir mit dem beliebtesten Algorithmus unter Studenten: Bubble Sort. Es ist ganz einfach: Der Algorithmus vergleicht zwei Elemente und vertauscht sie dann, wenn sie in der falschen Reihenfolge sind, und so weiter bis zum Ende des Arrays. Es stellt sich heraus, dass kleinere Elemente zum Ende des Arrays „schweben“ , wie Blasen in Limonade nach oben.
publicclassBubbleSort{publicstaticvoidbubbleSort(int[] myArray){int n = myArray.length;for(int i =0; i < n -1; i++){for(int j =0; j < n - i -1; j++){if(myArray[j]> myArray[j +1]){// Swap myArray[j] and myArray[j+1]int temp = myArray[j];
myArray[j]= myArray[j +1];
myArray[j +1]= temp;}}}}publicstaticvoidmain(String[] args){int[] arr ={18,28,2,7,90,45};System.out.println("Array before sorting:");for(int num : arr){System.out.print(num +" ");}bubbleSort(arr);System.out.println("\nArray after sorting:");for(int num : arr){System.out.print(num +" ");}}}
Hier verwendet die Methode ein Array von Ganzzahlen als Eingabe. Die äußere Schleife geht von 0 bis n-1. Hier ist n die Größe des Arrays. Die innere Schleife vergleicht benachbarte Elemente. Wenn die Reihenfolge falsch ist, werden sie von der Methode vertauscht. Dieser Vorgang wird wiederholt, bis das gesamte Array sortiert ist. Hier ist eine Ausgabe unseres Programms:
Array vor dem Sortieren: 18 28 2 7 90 45 Array nach dem Sortieren: 2 7 18 28 45 90
Auswahlsortierung
Der Auswahlalgorithmus sortiert ein Array, indem er wiederholt das kleinste Element aus dem unsortierten Teil findet und es am Anfang platziert. Schreiben wir es in Java:
publicclassSelectionSort{publicstaticvoidselectionSort(int[] myArray){int n = myArray.length;for(int i =0; i < n -1; i++){int minIndex = i;// Find the index of the minimum element in the unsorted part of the arrayfor(int j = i +1; j < n; j++){if(myArray[j]< myArray[minIndex]){
minIndex = j;}}// Swap the minimum element with the first element of the unsorted partint temp = myArray[minIndex];
myArray[minIndex]= myArray[i];
myArray[i]= temp;}}publicstaticvoidmain(String[] args){int[] arr ={18,28,45,2,90,7};System.out.println("Array before sorting:");for(int num : arr){System.out.print(num +" ");}selectionSort(arr);System.out.println("\nArray after sorting:");for(int num : arr){System.out.print(num +" ");}}}
Hier ist eine Ausgabe des Programms:
Array vor dem Sortieren: 18 28 45 2 90 7 Array nach dem Sortieren: 2 7 18 28 45 90
Lassen Sie es uns Schritt für Schritt erklären. Die äußere Schleife iteriert vom Anfang des Arrays bis zum vorletzten Element (bis zu n-1). Diese Schleife wählt jedes Element einzeln als Startpunkt des unsortierten Teils des Arrays aus . Innerhalb der äußeren Schleife initialisieren wir minIndex mit dem aktuellen Index i und gehen davon aus, dass es sich um den Index des kleinsten Elements im unsortierten Teil des Array handelt . Die innere Schleife beginnt bei i+1 und geht bis zum letzten Element des Arrays . Es sucht nach dem Index des kleinsten Elements im unsortierten Teil des Arrays , indem es jedes Element mit dem aktuellen Mindestelement ( arr[minIndex] ) vergleicht. Wenn wir ein Element finden, das kleiner als das aktuelle Mindestelement ist, aktualisieren wir minIndex auf den Index des neuen Mindestelements. Nachdem die innere Schleife abgeschlossen ist, haben wir den Index des minimalen Elements im unsortierten Teil des Array gefunden . Anschließend tauschen wir das minimale Element mit dem ersten Element des unsortierten Teils aus, indem wir eine temporäre Variable temp verwenden. Die äußere Schleife wird fortgesetzt, bis alle Elemente sortiert sind, wodurch der sortierte Teil des Array schrittweise erweitert wird . Schließlich wird das sortierte Array in der Hauptmethode vor und nach dem Aufruf der Methode „selectionSort“ gedruckt .
Zusammenführen, sortieren
Merge Sort ist ein Divide-and-Conquer-Algorithmus, der das Array rekursiv in kleinere Unterarrays aufteilt , diese sortiert und dann zusammenführt, um ein sortiertes Array zu erhalten. Merge Sort ist stabil und wird häufig verwendet, insbesondere wenn Stabilität und eine garantierte zeitliche Komplexität im ungünstigsten Fall erforderlich sind.
publicclassMergeSort{//Merge Sort arraypublicstaticvoidmergeSort(int[] myArray){if(myArray.length <=1){return;}int mid = myArray.length /2;int[] left =newint[mid];int[] right =newint[myArray.length - mid];System.arraycopy(myArray,0, left,0, mid);System.arraycopy(myArray, mid, right,0, myArray.length - mid);mergeSort(left);mergeSort(right);merge(myArray, left, right);}publicstaticvoidmerge(int[] arr,int[] left,int[] right){int i =0;// index for left subarrayint j =0;// index for right subarrayint k =0;// index for merged arraywhile(i < left.length && j < right.length){if(left[i]<= right[j]){
arr[k++]= left[i++];}else{
arr[k++]= right[j++];}}while(i < left.length){
arr[k++]= left[i++];}while(j < right.length){
arr[k++]= right[j++];}}publicstaticvoidmain(String[] args){int[] arr ={18,2,28,7,90,45};System.out.println("Array before sorting:");for(int num : arr){System.out.print(num +" ");}mergeSort(arr);System.out.println("\nArray after sorting:");for(int num : arr){System.out.print(num +" ");}}}
Die Ausgabe hier ist:
Array vor dem Sortieren: 18 2 28 7 90 45 Array nach dem Sortieren: 2 7 18 28 45 90
Lassen Sie uns genauer erklären, wie es funktioniert. Der Algorithmus teilt das Array rekursiv in zwei Teile, bis der Basisfall erreicht ist (wenn das Array ein oder null Elemente hat). Anschließend werden die sortierten Hälften mithilfe der Zusammenführungsmethode wieder zusammengeführt. Die Merge-Methode verwendet drei Arrays als Eingabe: das ursprüngliche Array sowie die linken und rechten Subarrays (links und rechts). Es vergleicht die Elemente aus dem linken und rechten Subarray und fügt sie in sortierter Reihenfolge in das ursprüngliche Array ein.
Sortieren durch Einfügen
Die Funktion „Einfügungssortierung“ besteht darin, dass ein Element aus dem unsortierten Teil wiederholt an der richtigen Position im sortierten Teil eingefügt wird. Es eignet sich gut für kleine Datensätze oder nahezu sortierte Daten.
publicclassInsertionSort{publicstaticvoidinsertionSort(int[] myArray){int n = myArray.length;for(int i =1; i < n; i++){int key = myArray[i];int j = i -1;while(j >=0&& myArray[j]> key){
myArray[j +1]= myArray[j];
j--;}
myArray[j +1]= key;}}publicstaticvoidmain(String[] args){int[] arr ={18,90,7,28,45,2};System.out.println("Array before sorting:");for(int num : arr){System.out.print(num +" ");}insertionSort(arr);System.out.println("\nArray after sorting:");for(int num : arr){System.out.print(num +" ");}}}
Die Ausgabe des Programms ist wie gewohnt:
Array vor dem Sortieren: 18 90 7 28 45 2 Array nach dem Sortieren: 2 7 18 28 45 90
Hier implementiert die Methode insertSort den Algorithmus Insertion Sort. Es durchläuft das Array und betrachtet jedes Element als Schlüssel. Es vergleicht den Schlüssel mit den Elementen davor und verschiebt sie um eine Position nach vorne, wenn sie größer sind. Dadurch werden die Elemente effektiv verschoben, um Platz für den Schlüssel an der richtigen Position zu schaffen.
Die äußere Schleife iteriert vom zweiten Element ( i = 1 ) bis zum letzten Element des Arrays. Die innere Schleife beginnt beim aktuellen Element ( arr[i] ) und geht rückwärts ( j = i - 1 ), bis sie die richtige Position für den Schlüssel findet oder den Anfang des Arrays erreicht . Wenn innerhalb der inneren Schleife ein Element ( arr[j] ) größer als der Schlüssel ist, wird es um eine Position nach vorne verschoben ( arr[j + 1] = arr[j] ), um Platz für den Schlüssel zu schaffen. Dieser Vorgang wird fortgesetzt, bis die richtige Position für den Schlüssel gefunden ist. Nachdem die innere Schleife abgeschlossen ist, wird der Schlüssel an der richtigen Position platziert ( arr[j + 1] = key ). In der Hauptmethode wird vor und nach der Sortierung mithilfe der Methode insertSort ein Beispielarray erstellt und gedruckt .
Schnelle Sorte
Quick Sort ist ein Divide-and-Conquer-Algorithmus, der ein Pivot-Element auswählt und das Array um den Pivot herum partitioniert. Aufgrund der geringen Konstantenfaktoren ist Quick Sort bei kleinen und mittleren Datensätzen in der Regel schneller als Merge Sort.
publicclassQuickSort{publicstaticvoidquickSort(int[] myArray,int low,int high){if(low < high){int pivotIndex =partition(myArray, low, high);quickSort(myArray, low, pivotIndex -1);quickSort(myArray, pivotIndex +1, high);}}publicstaticintpartition(int[] arr,int low,int high){int pivot = arr[high];int i = low -1;for(int j = low; j < high; j++){if(arr[j]<= pivot){
i++;swap(arr, i, j);}}swap(arr, i +1, high);return i +1;}publicstaticvoidswap(int[] arr,int i,int j){int temp = arr[i];
arr[i]= arr[j];
arr[j]= temp;}publicstaticvoidmain(String[] args){int[] arr ={18,28,2,90,7,45};System.out.println("Array before sorting:");for(int num : arr){System.out.print(num +" ");}quickSort(arr,0, arr.length -1);System.out.println("\nArray after sorting:");for(int num : arr){System.out.print(num +" ");}}}
Die Ausgabe ist hier:
Array vor dem Sortieren: 18 28 2 90 7 45 Array nach dem Sortieren: 2 7 18 28 45 90
Hier haben wir also drei Methoden, um eine schnelle Sortierung zu implementieren. Die QuickSort- Methode benötigt drei Parameter: das zu sortierende Array , den niedrigen Index des Subarrays und den hohen Index des Subarrays. Zunächst wird geprüft, ob das Subarray mehr als ein Element enthält. Wenn dies der Fall ist, wählt es einen Pivot mithilfe der Partitionsmethode aus, sortiert das Subarray rekursiv vor dem Pivot und das Subarray rekursiv nach dem Pivot. Die Partitionsmethode wählt den Pivot als letztes Element des Subarrays ( arr[high] ). Es setzt den Partitionsindex (i) auf den niedrigen Index minus 1. Anschließend iteriert es vom niedrigen Index zum hohen Index – 1 und prüft, ob jedes Element kleiner oder gleich dem Pivot ist. Wenn ja, tauscht es das Element mit dem Element am Partitionsindex (i) aus und erhöht den Partitionsindex. Schließlich tauscht es das Pivot-Element mit dem Element am Partitionsindex + 1 aus und gibt den Partitionsindex zurück. Die Partitionsmethode wählt den Pivot als letztes Element des Subarrays ( arr[high] ). Es setzt den Partitionsindex (i) auf den niedrigen Index minus 1. Anschließend iteriert es vom niedrigen Index zum hohen Index – 1 und prüft, ob jedes Element kleiner oder gleich dem Pivot ist. Wenn ja, tauscht es das Element mit dem Element am Partitionsindex (i) aus und erhöht den Partitionsindex. Schließlich tauscht es das Pivot-Element mit dem Element am Partitionsindex + 1 aus und gibt den Partitionsindex zurück. Die Swap-Methode ist eine Dienstprogrammmethode, mit der zwei Elemente im Array ausgetauscht werden . In der Hauptmethode wird vor und nach der Sortierung mit der Methode „quickSort“ ein Beispielarray erstellt und gedruckt .
Schlussfolgerungen
In diesem Artikel haben Sie herausgefunden, wie Sie ein Array in der Java-Sprache sortieren. Sie können eine integrierte Arrays.sort- Methode verwenden oder Ihre eigenen Implementierungen beliebter Sortiermethoden wie Blasensortierung, Zusammenführungssortierung usw. schreiben. Sie können auch versuchen, in Ihre eigene Sortiermethode einzudringen. Es hängt von Ihrer Aufgabe ab. Wenn Sie ein Sortierproblem schnell lösen müssen, verwenden Sie einfach eine vorgefertigte Methode. Wenn Sie Programmieren lernen und versuchen, darin besser zu werden, ist es eine wirklich gute Idee, selbst einige Sortiermethoden zu schreiben.
GO TO FULL VERSION