À propos de l'algorithme de tri JS Hill (tutoriel détaillé)

Cet article présente principalement les méthodes d'implémentation du tri Hill et du tri rapide de l'algorithme de tri JS. Il analyse les principes du tri Hill et du tri rapide et les techniques d'implémentation JavaScript sous forme d'exemples. Les amis dans le besoin peuvent s'y référer. 🎜>

Les exemples de cet article décrivent les méthodes d'implémentation du tri Hill et du tri rapide de l'algorithme de tri JS. Partagez-le avec tout le monde pour référence, comme suit :

Tri des collines :

Définissez une séquence d'intervalles, par exemple, 5, 3, 1. La première fois qu'il sera traité, tous les éléments avec un intervalle de 5 seront traités, la prochaine fois qu'il sera traité avec un intervalle de 3 et la dernière fois, il traitera les éléments avec un intervalle de 1. Autrement dit, les éléments adjacents effectuent un tri par insertion standard.

Lors du démarrage du dernier traitement, la plupart des éléments seront dans la bonne position et l'algorithme n'aura pas à échanger de nombreux éléments, ce qui est plus avancé que l'insertion d'éléments.

Complexité temporelle

O(n*logn)

function shellSort(){
  var N=arr.length;
  var h=1;
  while(h<N/3){
    h=3*h+1;//设置间隔
  }
  while(h>=1){
    for(var i=h; i<N; i++){
      for(j=i; j>=h && arr[j]<arr[j-h]; j-=h){
        swap(arr, j, j-h);
      }
    }
    h=(h-1)/3;
  }
}
function swap(array, i, j){//两个数调换
  var temp =array[j];
  array[j]=array[i];
  array[i]=temp;
}

Tri rapide :

Décomposez récursivement les données en différentes sous-séquences contenant des éléments plus petits et des éléments plus grands, et répétez cette étape jusqu'à ce que toutes les données soient ordonnées.

Choisissez une valeur de référence et placez la valeur inférieure à la valeur de référence dans un tableau. Ceux supérieurs à la valeur de référence sont placés dans un tableau.

Complexité temporelle

O(n*logn)

function quickSort(arr){
  if(arr.length==0){
    return [];
  }
  var left=[];
  var right=[];
  var p=arr[0];
  for(var i=1; i<arr.length; i++){
    if(arr[i]<p){
      left.push(arr[i]);
    }else{
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat(p,quickSort(right));
}

Ce qui précède est ce que j'ai compilé pour tout le monde. J'espère que cela sera utile à tout le monde à l'avenir.

Articles associés :

Que dire des valeurs nulles et fausses en javaScript

À propos des builds automatisés dans Webpack (tutoriel détaillé )

Comment implémenter une série de fonctions telles que le téléchargement d'images dans le mini programme WeChat

Comment créer un cadre de simulation de données universel pour le front end (tuto détaillé)

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!