Partager des exemples d'algorithmes courants de recherche, de tri et de déduplication implémentés avec JS

Cette fois, je partagerai avec vous des exemples d'algorithmes de recherche, de tri et de déduplication courants implémentés dans JS. Quelles sont les précautions pour la mise en œuvre d'algorithmes de recherche, de tri et de déduplication courants dans JS. cas pratiques. Levez-vous et jetez un œil.

Aujourd'hui, j'ai résumé un algorithme de tri simple

[Tri personnalisé]

Trouvez d'abord le plus petit nombre, puis comparez ce nombre avec d'autres nombres du tableau si vous le trouvez. un nombre plus petit que ce nombre, échangez les positions des deux nombres, puis continuez à trouver le prochain plus petit nombre pour le prochain tour de comparaison

var arr = [31, 6, 19, 8, 2, 3];
function findMin(start, arr) {
  var iMin = arr[start];
  var iMinIndex = start;
  for (var i = start + 1; i < arr.length; i++) {
    if (arr[i] < iMin) {
      iMin = arr[i];
      iMinIndex = i;
    }
  }
  return iMinIndex;
}
function sort1(arr) {
  for (var i = 0; i < arr.length; i++) {
    var iMinIndex = findMin(i, arr);
    var car;
    car = arr[i];
    arr[i] = arr[iMinIndex];
    arr[iMinIndex] = car;
  }
  return arr;
}
document.write(sort1(arr));

[Recherche linéaire] : recherchez un par un

//不重复 有序
var arr = [0];
for (var i = 1; i < 100000; i++) {
  arr[i] = arr[i - 1] + Math.floor(Math.random() * 4 + 1);
}
function find1(n, arr) {
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] == n) {
      return true;
    }
  }
  return false;
}
//测试性能
var t1 = new Date().getTime();
for (var i = 0; i < 10000; i++) {
  var n = Math.random() * 10000;
  find2(n, 0, arr.length - 1)
}
alert(new Date().getTime() - t1);

[Recherche binaire] : Divisez constamment en deux parties, et rechercher en parties

est une méthode universelle, pas nécessairement la meilleure, mais une méthode garantie. (Méthode Diviser pour mieux régner)

*** Additionnez les valeurs moyennes et divisez par deux, uniformément vers la gauche, arrondissez à l'inférieur

//不重复 有序
var arr = [12, 17, 23, 34, 45, 76, 89];
function find2(n, s, e) {
  //边界处理
  if (s > e) {
    return false;
  } else if (s == e) {
    if (arr[s] == n) {
      return true;
    } else {
      return false;
    }
  }
  var c = Math.floor((s + e) / 2);
  if (arr[c] == n) {
    return true;
  } else {
    if (n < arr[c]) {
      return find2(n, s, c);
    } else {
      return find2(n, c + 1, e);
    }
  }
}
alert(find2(34, 0, arr.length - 1)); //true false

[Traitement des limites]---- -Récursion, recherchez-le couche par couche

//要求数组不重复有顺序\
var arr = [12, 23, 34, 45, 56, 67, 78]
function find2(n, s, e) {
  if (s > e) {
    return fasle;
  } else if (s == e) {
    if (arr[s] == e) {
      return true;
    } else {
      return false;
    }
  }
  var c = Math.floor((s + e) / 2);
  if (arr[c] == n) {
    return true;
  } else {
    if (n < arr[c]) {
      return find2(n, s, c);
    } else {
      return find2(n, c + 1, e);
    }
  }
}
alert(find2(12, arr.length + 1, 78));

Appliquer

[Trouver la valeur minimale]

var arr = [12, 54, 32, 9, 5, 3, 1, 101, -100, -1000];
function findMin(s, e) {
  if (s > e) {
    return [];
  } else if (s == e) {
    return arr[s];
  } else if (s == e - 1) {
    if (arr[s] < arr[e]) {
      return arr[s];
    } else {
      return arr[e];
    }
  }
  var c = Math.floor((s + e) / 2);
  var l = findMin(s, c);
  var r = findMin(c + 1, e);
  if (l < r) {
    return l;
  } else {
    return r;
  }
}
alert(findMin(0, arr.length - 1));

[Déduplication de tableau]

var arr = [1, 2, 3, 4, 5, 4, 3, 4, 5, 2, 1, 4, 2, 1, 5, 7];
function findInArr(n, arr) {
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] == n) {
      return true;
    }
  }
  return false;
}
function removeCopy(s, e) {
  if (s > e) {
    return [];
  } else if (s == e) {
    return [arr[s]];
  } else if (s == e - 1) {
    if (arr[s] == arr[e]) {
      return [arr[s]];
    } else {
      return [arr[s], arr[e]]
    }
  }
  var c = Math.floor((s + e) / 2);
  var l = removeCopy(s, c);
  var r = removeCopy(c + 1, e);
  for (var i = 0; i < r.length; i++) {
    if (!findInArr(r[i], l)) {
      l.push(r[i]);
    }
  }
  return l;
}
document.write(removeCopy(0, arr.length - 1));

[Array Sort]

var arr = [34, 32, 1, 76, 55, -100, 99, 101];
function mySort(s, e) {
  //边界处理
  if (s > e) {
    return [];
  } else if (s == e) {
    return [arr[s]]
  } else if (s == e - 1) {
    if (arr[s] < arr[e]) {
      return [arr[s], arr[e]];
    } else {
      return [arr[e], arr[s]];
    }
  }
  //1.切中间值
  var c = Math.floor((s + e) / 2);
  //2.分半处理
  var l = mySort(s, c);
  var r = mySort(c + 1, e);
  var res = [];
  while (l.length > 0 || r.length > 0) {
    if (l[0] < r[0]) {
      res.push(l.shift());
    } else {
      res.push(r.shift());
    }
  }
  if (l.length == 0) {
    res = res.concat(r);
  } else if (r.length == 0) {
    res = res.concat(l);
  }
  return res;
}
//调用
document.write(mySort(0, arr.length - 1));

Bubble Sort BubbleSort

boucles, en retirant deux valeurs à chaque fois et en les comparant If. la valeur suivante est inférieure à la valeur actuelle, puis la position est échangée

La boucle externe est une boucle pour prendre le nombre, et la boucle interne est une comparaison d'échange par paires

var arr = [ - 122, -2, 5, 6, 73, 34, 5, 2];
function BubbleSort(arr) {
  for (var i = 0; i < arr.length; i++) {
    for (var j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        var tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp
      }
    }
  }
  return arr;
}
document.write(BubbleSort(arr));

[Tri rapide] --- ----quickSort

Prenez le nombre au milieu du tableau, mettez le nombre plus petit que le nombre du milieu sur le côté gauche du nombre du milieu, mettez le nombre plus grand que le numéro du milieu sur le côté droit, puis liez les deux fois

function quickSort(arr, s, e) {
  //边界处理 参与流程
  if (arr.length == 0) {
    return [];
  }
  var c = Math.floor((s + e) / 2);
  var arrC = arr.splice(c, 1);
  var l = [];
  var r = [];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < arrC) {
      l.push(arr[i]);
    } else {
      r.push(arr[i]);
    }
  }
  return quickSort(l).concat(arrC, quickSort(r));
}
var arr = [5, 5, 12, 56, 1, 67, -1, -23 - 1];
document.write(quickSort(arr, 0, arr.length - 1));

[Hash] tableau de hachage de hachage------structure couramment utilisée dans js

Ajouter

var arr = [];
arr.length = 0;
var cont = 0;
function hash_add(n) {
  var pos = n % arr.length;
  //当空间不足的时候
  if (arr[pos]) {
    while (arr[pos]) {
      cont++;
      if (arr[pos] == n) {
        return;
      } else {
        pos++;
        if (pos == arr.length) {
          pos = 0;
        }
      }
    }
    arr[pos] = n;
  } else {
    arr[pos] = n;
  }
  //空间不足的时候的扩建
  if (cont == arr.length) {
    //d等呗扩建
    var oldArr = arr;
    arr.length = oldArr.length * 2;
    arr = [];
    for (var i = 0; i < oldArr.length; i++) {
      arr.push(oldArr[i]);
      count = 0;
    }
  }
}
hash_add();

Je pense que vous maîtrisez la méthode après avoir lu le cas dans cet article, venez pour des informations plus intéressantes. Faites attention aux autres articles connexes sur le site Web chinois de php !

Lecture recommandée :

Explication détaillée des cas d'utilisation de la fonction de rappel JavaScript

Analyse des étapes de publication des composants vue sur npm

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!