Comment implémenter le tri JS Hill et le tri rapide

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. J'espère que cela pourra aider tout le monde.

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é temporelleO(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 de manière récursive les données en différentes sous-séquences contenant des éléments plus petits et des éléments plus grands. Répétez cette étape jusqu'à ce que toutes les données soient en ordre.

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é temporelleO(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));
}

Le tri rapide convient aux grandes collections de données, mais les performances diminueront lors du traitement de petits ensembles de données.

Recommandations associées :

Analyse détaillée de la méthode d'implémentation de l'algorithme de tri Hill en PHP

Tri Hill du tri JavaScript algorithme 2 exemples_Connaissances de base

Tri JavaScript Hill, tri rapide, tri par fusion algorithm_compétences javascript

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!