Explication détaillée du code sur la façon dont JavaScript implémente le tri rapide

Le contenu de cet article est de partager avec vous comment implémenter le tri rapide en JavaScript. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer

J'ai vu par hasard. Blog du professeur Ruan Yifeng Un algorithme de tri rapide utilisé il y a quelques années en Chine créait deux tableaux supplémentaires à chaque fois qu'il était bouclé. Si la quantité de données est importante, cela occupera beaucoup de mémoire supplémentaire. Cependant, les tableaux sont des types référence et peuvent être modifiés. Le tableau d'origine lui-même peut être directement manipulé pour économiser de la mémoire.

La clé de la méthode de tri rapide est de sélectionner une valeur et de diviser l'ensemble du tableau en deux parties, la plus petite à gauche et la plus grande à droite. Voici comment cette fonction est écrite :

//该函数的主要目的是交换数组中两个元素的位置
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值最终的位置
}

En observant la partition de l'algorithme de regroupement, il n'est pas difficile de constater qu'en fait, il y a toujours une valeur clé stockée dans les positions i et j, puis elle est échangée avec une valeur supérieure ou inférieure à il. Ensuite, nous pouvons également l'écrire comme une méthode de regroupement à sens unique :

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值最终的位置
}

Ensuite, appelez la fonction de regroupement de manière récursive pour trier l'ensemble du tableau :

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);
    }
}

Recommandations associées :

Résumé de mise en œuvre et d'optimisation de deux méthodes de tri rapide

Principe de tri rapide et java implémentation

Implémentation C++ du tri rapide

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!