Wie Sie Suchalgorithmen und Sortieralgorithmen in der Java-Programmierung schnell beherrschen

1. Suchalgorithmus

Binärer Algorithmus

Die binäre Suche, auch als binäre Suche bekannt, ist ein effizienter Suchalgorithmus. Seine Grundidee ist: Teilen Sie das geordnete Array (oder die Menge) in zwei Teile. Wenn das aktuelle mittlere Element dem Zielelement entspricht, ist die Suche erfolgreich. Wenn das aktuelle mittlere Element größer als das Zielelement ist, wird die linke Hälfte durchsucht ; wenn das aktuelle mittlere Element kleiner ist als Suchen Sie für das Zielelement nach der rechten Hälfte. Wiederholen Sie die obigen Schritte, bis das Zielelement gefunden wird oder der Suchbereich leer ist und die Suche fehlschlägt.

Das Folgende ist ein in Java implementierter binärer Algorithmus:

public static int binarySearch(int[] arr, int target) {
    if (arr == null || arr.length == 0) {
        return -1;
    }
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

Die obige Methode verwendet einen Satz geordneter ganzzahliger Arrays und einen Zielwert als Parameter und gibt den Index des Zielwerts im Array zurück; im Array vorhanden sind, geben Sie einfach -1 zurück.

Der Kern des Algorithmus ist die while-Schleife, die wiederholt ausgeführt wird, wenn links und rechts bestimmte Bedingungen erfüllen:

• Wenn Mitte gleich Ziel ist, wird Mitte zurückgegeben und der Algorithmus endet.

• Wenn Mitte ist größer als das Ziel, dann setzen Sie die Suche auf der linken Seite fort, d. h. setzen Sie rechts auf Mitte - 1;

• Bei jedem Durchlauf der Schleife verwenden wir mid = left + (right - left) / 2, um den Index des mittleren Elements zu berechnen. Es ist zu beachten, dass wir die Form von links + rechts und nicht die Form von (links + rechts) / 2 verwenden müssen, da es sonst zu Ganzzahlüberlaufproblemen kommen kann.

2. Sortieralgorithmus

In Java wird der Sortieralgorithmus durch Implementierung der Comparable- oder Comparator-Schnittstelle implementiert. Hier sind einige häufig verwendete Sortieralgorithmen und ihre Implementierungsmethoden:

Bubble Sort

Bubble Sort ist ein einfacher Sortieralgorithmus. Die Idee besteht darin, zwei benachbarte Elemente ständig zu vergleichen und bei falscher Reihenfolge die Positionen zu tauschen. Dieser Vorgang ähnelt dem kontinuierlichen Aufsteigen von Wasserblasen und wird daher als Blasensortierung bezeichnet.

public static void bubbleSort(int[] arr) {
    int temp;
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                //交换位置
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Auswahlsortierung

Die Idee der Auswahlsortierung besteht darin, das kleinste Element aus den unsortierten Elementen auszuwählen und es am Ende der Sortierung zu platzieren. Jedes Mal, wenn das kleinste Element gefunden wird, wird es mit dem aktuell unsortierten ersten Element ausgetauscht.

public static void selectionSort(int[] arr) {
    int minIndex;
    for (int i = 0; i < arr.length - 1; i++) {
        minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        //交换位置
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

Einfügesortierung

Die Idee der Einfügesortierung besteht darin, unsortierte Elemente an der entsprechenden sortierten Position einzufügen. Wählen Sie ein Element aus den unsortierten Elementen aus und durchlaufen Sie die sortierten Elemente von hinten nach vorne. Bewegen Sie sich eine Position nach hinten und fahren Sie mit dem Vergleich fort, bis Sie eine Position finden, die kleiner als das unsortierte Element ist an diesem Ort.

public static void insertionSort(int[] arr) {
    int preIndex, current;
    for (int i = 1; i < arr.length; i++) {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
}

Schnellsortierung

Schnellsortierung ist ein Sortieralgorithmus, der auf dem Prinzip „Teile und herrsche“ basiert. Es wählt einen Pivotpunkt aus, teilt das Array in zwei Subarrays auf, die kleiner oder gleich dem Pivotpunkt und größer als der Pivotpunkt sind, und sortiert dann die beiden Subarrays rekursiv.

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int i = left, j = right, pivot = arr[left];
        while (i < j) {
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            if (i < j) {
                arr[i++] = arr[j];
            }
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            if (i < j) {
                arr[j--] = arr[i];
            }
        }
        arr[i] = pivot;
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
}

Das obige ist der detaillierte Inhalt vonWie Sie Suchalgorithmen und Sortieralgorithmen in der Java-Programmierung schnell beherrschen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!