Quelques méthodes de tri couramment utilisées pour les tableaux js

Cet article partage principalement avec vous quelques méthodes de tri couramment utilisées pour les tableaux js, notamment le tri à bulles, le tri rapide, le tri par insertion, etc. J'espère qu'il pourra vous aider.

1. Tri des bulles (de l'arrière vers l'avant)

var array = [1,4,-8,-3,6,12,9,8];function sort(arr){    for(var j=0;j<arr.length-1;j++){    //两两比较，如果前一个比后一个大，则交换位置。
       for(var i=0;i<arr.length-1-j;i++){            if(arr[i]>arr[i+1]){                var temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        } 
    }
}
sort(array);
document.write(array);

(1) Comparez les éléments adjacents. Si le premier est plus grand que le second, échangez leurs positions.

(2) Faites le même travail pour chaque paire d'éléments adjacents, de la première paire du début à la dernière paire à la fin. À ce stade, le dernier élément doit être le plus grand nombre.

(3) Répétez les étapes ci-dessus pour tous les éléments sauf le dernier.

(4) Continuez à répéter les étapes ci-dessus pour de moins en moins d'éléments à chaque fois jusqu'à ce qu'il n'y ait plus de paire de nombres à comparer.

2. Tri rapide : pensée récursive, tri rapide des deux côtés, amélioration du tri à bulles

var array = [1,4,-8,-3,6,12,9,8];
function quickSort(arr){//如果数组长度小于等于1，则返回数组本身
   if(arr.length<=1){        return arr;
   }    //定义中间值的索引
   var index = Math.floor(arr.length/2);    //取到中间值
   var temp = arr.splice(index,1);    //定义左右部分数组
   var left = [];    var right = [];    for(var i=0;i<arr.length;i++){    //如果元素比中间值小，那么放在左边，否则放右边
       if(arr[i]<temp){            left.push(arr[i]);
       }else{            right.push(arr[i]);
       }
   }    return quickSort(left).concat(temp,quickSort(right));
}
document.write(quickSort(array));

Math.floor(x ) arrondit à l'inférieur et renvoie l'entier le plus proche inférieur ou égal à x.

La méthode splice(index,num,item) ajoute des éléments au tableau ou supprime des éléments du tableau et renvoie l'élément supprimé.

index est un entier, l'emplacement de l'élément opéré (obligatoire)

num est un entier, le nombre d'éléments à supprimer , si 0, signifie ne pas supprimer (obligatoire)

l'élément est un nouvel élément ajouté au tableau, qui peut être multiple (facultatif)

La méthode push() ajoute un ou plusieurs nouveaux éléments à la fin du tableau et renvoie la longueur du nouveau tableau

La méthode concat() connecte deux ou plusieurs tableaux sans en changeant le tableau d'origine, renvoie un nouveau tableau

3. Tri par insertion

var array = [1,4,-8,-3,6,12,9,8];function insertSort(arr){
//假设第0元素是有序序列，第1元素之后是无序的序列。从第1元素开始依次将无序序列的元素插入到有序序列中
   for(var i=1; i<arr.length;i++){        if(arr[i]<arr[i-1]){            //取出无序序列中需要插入的第i个元素
           var temp = arr[i];            //定义有序中的最后一个位置
           var j = i-1;
           arr[i] = arr[j];            //比较大小，找到插入的位置
           while(j>=0&&temp<arr[j]){
               arr[j+1] = arr[j];
               j--;
           };            //插入
           arr[j+1] = temp;
       }
   }
 }
insertSort(array)
document.write(array);

(1) À partir du premier élément, le l'élément peut Considéré comme ayant été trié

(2) Sortir l'élément suivant et scanner

(3) Si l'élément (trié) est supérieur au nouvel élément, déplacez l'élément à la position suivante

(4) Répétez l'étape 3 jusqu'à ce que vous trouviez la position où l'élément trié est inférieur ou égal au nouvel élément

(5) Insérez le nouvel élément dans la position suivante

(6) Répétez l'étape 2

4. Tri par sélection

var array = [1,4,-8,-3,6,12,9,8];function selectSort(arr){    for(var i=0;i<arr.length;i++){        //设置当前范围最小值和索引
       var min = arr[i];        var minIndex = i;        //在该范围选出最小值
       for(var j=i+1;j<arr.length;j++){            if(min>arr[j]){
               min = arr[j];
               minIndex = j;
           }
       }        //将最小值插入,并将原来位置的最小值删除
       arr.splice(i,0,min);
       arr.splice(minIndex+1,1);
   }
}
selectSort(array);
document.write(array);

(1) Trouver le plus petit (grand) élément dans la séquence non triée

(2 ) Et stockez-le à la position de départ de la séquence triée

(3) Ensuite, continuez à trouver le plus petit (grand) élément parmi les éléments non triés restants

(4) puis placez-le à la fin de la séquence triée.

(5) et ainsi de suite

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!