Detaillierte Code-Erklärung, wie JavaScript die schnelle Sortierung implementiert

Der Inhalt dieses Artikels soll Ihnen zeigen, wie Sie eine schnelle Sortierung in JavaScript implementieren. Er hat einen gewissen Referenzwert.

Ich habe ihn versehentlich gesehen Der Blog von Lehrer Ruan Yifeng Ein schneller Sortieralgorithmus aus China hat bei jeder Schleife zwei zusätzliche Arrays erstellt. Wenn die Datenmenge groß ist, wird viel zusätzlicher Speicher beansprucht. Arrays sind jedoch Referenztypen und können geändert werden. Das ursprüngliche Array selbst kann direkt manipuliert werden, um Speicherplatz zu sparen.

Der Schlüssel zur Schnellsortierungsmethode besteht darin, einen Wert auszuwählen und das gesamte Array in zwei Teile zu teilen, den kleineren links und den größeren rechts. So wird diese Funktion geschrieben:

//该函数的主要目的是交换数组中两个元素的位置
function swap(arr, index1, index2) {

    let data = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = arr[index1];

    //数组是引用类型，允许修改原数组。
}

//选取随机值，将数组分为两部分
function partition(arr, start, end) {
    let keyIndex = end,
        key = arr[keyIndex]; //将随机值(以后称key值)定为最后一个数，也可以真的随机选取，见下一行
    // let keyIndex = Math.floor(Math.random() * (end - start)) + start;

    let i = start,
        j = end,
        order = true;
    //当order为true时正向筛选，当order为false时逆向筛选
    //先从正向开始，因为我们把key值保存到了数组的结尾处。
    while(i != j) {
        if(order) {
            //正向筛选
            if (arr[i]>key) {
                swap(arr, i, j); //将大于key的数字和key进行交换
                order = false;
            } else {
                i++;
            }

        } else {
            //逆向筛选
            if(arr[j]<key) {
                swap(arr, i, j); //将小于key的数字和key进行交换
                order = true;
            } else {
                j--;
            }
        }
    }
    return i;//返回key值最终的位置
}

Wenn man die Partition des Gruppierungsalgorithmus betrachtet, ist es nicht schwer festzustellen, dass tatsächlich immer ein Schlüsselwert an den Positionen i und j gespeichert ist und dieser dann durch einen Wert ausgetauscht wird, der größer oder kleiner ist Es. Dann können wir es auch als Einweg-Gruppierungsmethode schreiben:

function partition2(arr, start, end) {
    let keyIndex = end,
        key = arr[end];
    let i = start -1,
        j = start;
    for (;j<end;j++) {
        if (arr[j]< key) {
        // i位置的值永远比key值小
            i++;
            if (i != j) {
                swap(arr, i, j);
            }
        }
    } 
    ++i;
    swap(arr, i, end);

    return i; //返回key值最终的位置
}

Rufen Sie als Nächstes die Gruppierungsfunktion rekursiv auf, um das gesamte Array zu sortieren:

function quickSort(arr, start, end) {
    if (start == end) return;
    let index = partition(arr, start, end);
    if (index > start){
        quickSort(arr, start, index-1);
    }
    if (index<end) {
        quickSort(arr, index+1, end);
    }
}

Verwandte Empfehlungen :

Zusammenfassung der Implementierung und Optimierung zweier Methoden der Schnellsortierung

Schnellsortierungsprinzip und Java Implementierung

C++-Implementierung der Schnellsortierung

Das obige ist der detaillierte Inhalt vonDetaillierte Code-Erklärung, wie JavaScript die schnelle Sortierung implementiert. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!