Beispiele für Sortiermethoden in Java

Blasensortierung

Merkmale: geringe Effizienz, einfache Umsetzung

Ideen (von klein bis groß): Jeder Move the größtes Element in der Sequenz, das bis zum Ende sortiert werden soll, und der Rest ist die neue zu sortierende Sequenz. Wiederholen Sie die obigen Schritte, bis alle Elemente sortiert sind. Dabei handelt es sich lediglich um eine Art Blasensortierung, natürlich kann auch von hinten nach vorne sortiert werden.

public void bubbleSort(int array[]) {
        int t = 0;        
        for (int i = 0; i < array.length - 1; i++)            
        for (int j = 0; j < array.length - 1 - i; j++)                
        if (array[j] > array[j + 1]) {
                    t = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = t;
                }
    }

Auswahlsortierung

Eigenschaften: geringe Effizienz, einfach zu implementieren

Idee: Wählen Sie die kleinste aus der zu sortierenden Sequenz aus In jedem Durchgang werden die Elemente am Ende der sortierten Sequenz platziert und die verbleibenden Bits müssen noch sortiert werden. Wiederholen Sie die obigen Schritte, bis die Sortierung abgeschlossen ist.

public void selectSort(int array[]) {
        int t = 0;        
        for (int i = 0; i < array.length - 1; i++)            
        for (int j = i + 1; j < array.length; j++)                
        if (array[i] > array[j]) {
                    t = array[i];
                    array[i] = array[j];
                    array[j] = t;
                }
    }

Einfügungssortierung

Eigenschaften: Geringe Effizienz, einfach zu implementieren

Idee: Teilen Sie das Array in zwei Teile und teilen Sie diese auf Teil der Elemente. Vergleichen Sie es nacheinander mit den vorherigen Elementen. Wenn das aktuelle Elementarray [i] klein ist, ersetzen Sie es. Finden Sie eine vernünftige Position und fügen Sie ein Array ein[i]

public void insertionSort(int array[]) {
        int i, j, t = 0;        
        for (i = 1; i < array.length; i++) {
            t = array[i];            
            for (j = i - 1; j >= 0 && t < array[j]; j--)
                array[j + 1] = array[j];
            array[j + 1] = t;
        }
    }

schnelle Sortierung

Eigenschaften: effizient, zeitliche Komplexität ist nlogn.

Übernehmen Sie die Idee der Teile-und-Herrsche-Methode: Legen Sie zunächst einen Achsenwert-Pivot fest und verwenden Sie dann diesen Achsenwert als Teilungsbasis, um die zu sortierende Sequenz in zwei Teile zu teilen, die größer als der Pivot und kleiner sind als der Pivot, und dividieren Sie dann die geteilte Untersequenz. Die Sequenz wird schnell sortiert, bis die Untersequenz ein Element enthält.

public void quickSort(int array[], int low, int high) {// 传入low=0，high=array.length-1;
        int pivot, p_pos, i, t;// pivot->位索引;p_pos->轴值。        
        if (low < high) {
            p_pos = low;
            pivot = array[p_pos];            
            for (i = low + 1; i <= high; i++)                
            if (array[i] > pivot) {
                    p_pos++;
                    t = array[p_pos];
                    array[p_pos] = array[i];
                    array[i] = t;
                }
            t = array[low];
            array[low] = array[p_pos];
            array[p_pos] = t;            // 分而治之
            quickSort(array, low, p_pos - 1);// 排序左半部分
            quickSort(array, p_pos + 1, high);// 排序右半部分
        }

Empfohlenes Tutorial: Java-Tutorial

Das obige ist der detaillierte Inhalt vonBeispiele für Sortiermethoden in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!