Maison > interface Web > js tutoriel > le corps du texte

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

亚连
Libérer: 2018-06-21 11:29:00
original
1761 Les gens l'ont consulté

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;
}
Copier après la connexion

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));
}
Copier après la connexion
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!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal