Introduction à quelques algorithmes de base courants en JS

Un algorithme est simplement une fonction qui convertit l'entrée d'une certaine structure de données en sortie d'une certaine structure de données. La logique interne de l'algorithme détermine comment convertir.

Algorithme de base

Tri

1. Tri à bulles

//冒泡排序function bubbleSort(arr) {
  for(var i = 1, len = arr.length; i < len - 1; ++i) { 
     for(var j = 0; j <= len - i; ++j) {    
       if (arr[j] > arr[j + 1]) {     
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

2. Tri par insertion

//插入排序 过程就像你拿到一副扑克牌然后对它排序一样
function insertionSort(arr) {
  var n = arr.length;  
// 我们认为arr[0]已经被排序，所以i从1开始
  for (var i = 1; i < n; i++) {  
// 取出下一个新元素，在已排序的元素序列中从后向前扫描来与该新元素比较大小
    for (var j = i - 1; j >= 0; j--) {   
        if (arr[i] >= arr[j]) { // 若要从大到小排序，则将该行改为if (arr[i] <= arr[j])即可
        // 如果新元素arr[i] 大于等于 已排序的元素序列的arr[j]，
        // 则将arr[i]插入到arr[j]的下一位置，保持序列从小到大的顺序
        arr.splice(j + 1, 0, arr.splice(i, 1)[0]);       
        // 由于序列是从小到大并从后向前扫描的，所以不必再比较下标小于j的值比arr[j]小的值，退出循环
        break;  
      } else if (j === 0) {        
      // arr[j]比已排序序列的元素都要小，将它插入到序列最前面
        arr.splice(j, 0, arr.splice(i, 1)[0]);
      }
    }
  } 
   return arr;
}

Lorsque l'objectif est un tri ascendant, le meilleur des cas est que la séquence est déjà triée par ordre croissant ordre, alors il n'a besoin d'être comparé que n-1 fois et la complexité temporelle est O(n). Le pire des cas est que la séquence est à l'origine triée par ordre décroissant, donc n(n-1)/2 fois doivent être comparés et la complexité temporelle est O(n^2).

Donc, en moyenne, la complexité temporelle du tri par insertion est O(n^2). De toute évidence, la complexité temporelle du niveau de puissance signifie que le tri par insertion n'est pas adapté aux situations où il y a beaucoup de données. De manière générale, le tri par insertion est adapté au tri de petites quantités de données.

3. Tri rapide

//快速排序
function qSort(arr) {
  //声明并初始化左边的数组和右边的数组
  var left = [], right = [];
 //使用数组第一个元素作为基准值
  var base = arr[0];  
 //当数组长度只有1或者为空时，直接返回数组，不需要排序
  if(arr.length <= 1) return arr;  
 //进行遍历
  for(var i = 1, len = arr.length; i < len; i++) {
    if(arr[i] <= base) {    
    //如果小于基准值，push到左边的数组
      left.push(arr[i]);
    } else {    
    //如果大于基准值，push到右边的数组
      right.push(arr[i]);
    }
  }
  //递归并且合并数组元素
  return [...qSort(left), ...[base], ...qSort(right)];
    //return qSort(left).concat([base], qSort(right));}

Supplément :

Dans ce code, on peut voir que ceci Le code réalise la distinction les parties gauche et droite via pivot, puis continue récursivement le tri par pivot sur les parties gauche et droite, réalisant la description textuelle du tri rapide, ce qui signifie qu'il n'y a aucun problème dans la mise en œuvre de cet algorithme.

Bien que cette implémentation soit très simple à comprendre. Cependant, cette implémentation peut également être améliorée. Dans cette implémentation, nous avons constaté que deux tableaux gauche/droite sont définis dans la fonction pour stocker les données temporaires. À mesure que le nombre de récursions augmente, de plus en plus de données temporaires seront définies et stockées, nécessitant Ω(n) d'espace de stockage supplémentaire.

Par conséquent, comme dans de nombreuses introductions d'algorithmes, la version de partitionnement sur place est utilisée pour implémenter le tri rapide. Présentons d'abord ce qu'est un algorithme de partitionnement sur place.

Description de l'algorithme de partitionnement sur place

• Sélectionnez un élément du tableau, appelé "pivot", la position du premier élément du tableau est utilisé comme index.

• Parcourez le tableau. Lorsque le numéro du tableau est inférieur ou égal à la valeur de base, le nombre à la position d'index est échangé avec le nombre et l'index est +1

• Échangez la valeur de base avec la position actuelle de l'index

Après les 3 étapes ci-dessus, la valeur de base sera centrée et les chiffres à gauche et les côtés droits du tableau sont plus petits que la valeur de base ou Big. À ce stade, le tableau trié peut être obtenu par partitionnement récursif sur place.

Implémentation d'un algorithme de partitionnement sur place

// 交换数组元素位置
function swap(array, i, j) {
    var temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}
function partition(array, left, right) {
    var index = left;
    var pivot = array[right]; // 取最后一个数字当做基准值，这样方便遍历
    for (var i = left; i < right; i++) {
    if (array[i] <= pivot) {
        swap(array, index, i);
        index++;
     }
 }
     swap(array, right, index);
     return index;
     }

Parce que nous devons partitionner de manière récursive sur place plusieurs fois, et en même temps, nous ne voulons pas de partitionnement supplémentaire espace d'adressage, donc lors de la mise en œuvre de l'algorithme de partitionnement, il y aura trois paramètres, à savoir le tableau d'origine, le point de départ du tableau à parcourir à gauche et le point final du tableau à parcourir à droite.

Enfin, une valeur d'index triée est renvoyée pour la prochaine récursion. La valeur correspondant à cet index doit être plus petite que l'élément du tableau à gauche de l'index et plus grande que tous les éléments du tableau à droite. .

En gros, encore une fois, nous pouvons optimiser davantage l'algorithme de partitionnement. Nous avons constaté que

Partitionnement sur place. la version est rapide Implémentation du tri

function quickSort(array) {
    function swap(array, i, j) {
       var temp = array[i];
       array[i] = array[j];
       array[j] = temp;
     }
     function partition(array, left, right) {
        var index = left;
        var pivot = array[right]; // 取最后一个数字当做基准值，这样方便遍历
         for (var i = left; i < right; i++) {
             if (array[i] < pivot) {
                 swap(array, index, i);
                 index++;
           }
      }
      swap(array, right, index);        
      return index;
      }
      function sort(array, left, right) {    
          if (left > right) {        
              return;
        }        
        var storeIndex = partition(array, left, right);
        sort(array, left, storeIndex - 1);
        sort(array, storeIndex + 1, right);
    }

    sort(array, 0, array.length - 1);    
    return array;
}

2. Chaîne

1. Chaîne palindrome

//判断回文字符串
function palindrome(str) {
  var reg = /[\W\_]/g;  
  var str0 = str.toLowerCase().replace(reg, "");  
  var str1 = str0.split("").reverse().join("");  
  return str0 === str1;
}

2. Retournez la chaîne

function reverseString(str) {
  return str.split("").reverse().join("");
}

3 Le caractère qui apparaît le plus de fois dans la chaîne

function findMaxDuplicateChar(str) {
  var cnt = {}, //用来记录所有的字符的出现频次
      c = ''; //用来记录最大频次的字符
  for (var i = 0; i < str.length; i++) {
      var ci = str[i];    
      if (!cnt[ci]) {
      cnt[ci] = 1;
    } else {
      cnt[ci]++;
    }    
      if (c == &#39;&#39; || cnt[ci] > cnt[c]) {
      c = ci;
    }
  }  
      console.log(cnt)  return c;
}

3. Tableau

1. Déduplication du tableau

//数组去重
function uniqueArray(arr) {
  var temp = [];  
  for (var i = 0; i < arr.length; i++) {
      if (temp.indexOf(arr[i]) == -1) {
      temp.push(arr[i]);
    }
  } 
      return temp;  
      //or
  return Array.from(new Set(arr));
}

4. Recherche

1. Recherche binaire

//二分查找
function binary_search(arr, l, r, v) {
  if (l > r) {  
    return -1;
  }  
   var m = parseInt((l + r) / 2);  
   if (arr[m] == v) {  
     return m;
  } else if (arr[m] < v) {  
       return binary_search(arr, m+1, r, v);
  } else {   
        return binary_search(arr, l, m-1, v);
  }
}

Appliquez la recherche binaire au tri par insertion précédent pour former un tri par insertion binaire, ce qui améliorerait l'efficacité. Mais lorsque j'ai testé, la quantité de données était peut-être trop petite et je n'ai pas trouvé d'écart trop évident. . Vous pouvez l'essayer vous-même ~ (par exemple, utilisez console.time('insertion sorting time-consumer') et console.timeEnd('insertion sorting time-consumer') au début et à la fin de l'appel de fonction)

5. Recherche/traversée d'arbre

1. Recherche en profondeur d'abord

//深搜 非递归实现
function dfs(node) {
  var nodeList = [];  
  if (node) {  
    var stack = [];
    stack.push(node);   
     while(stack.length != 0) {   
        var item = stack.pop();
      nodeList.push(item);      
        var children = item.children;      
        for (var i = children.length-1; i >= 0; i--) {
             stack.push(children[i]);
      }
    }
  }  return nodeList;
} 
//深搜 递归实现
function dfs(node, nodeList) { 
 if (node) {
    nodeList.push(node);    
 var children = node.children;    
 for (var i = 0; i < children.length; i++) {
      dfs(children[i], nodeList);
    }
  }  
 return nodeList;
}

2. Recherche en largeur

//广搜 非递归实现
function bfs(node) {
    var nodeList = [];    
    if (node != null) {     
       var queue = [];
       queue.unshift(node);        
       while (queue.length != 0) {     
           var item = queue.shift();
            nodeList.push(item);            
           var children = item.children;           
            for (var i = 0; i < children.length; i++)
                queue.push(children[i]);
        }
    }    
        return nodeList;
}
//广搜 递归实现
var i=0;  
//自增标识符
function bfs(node, nodeList) {  
  if (node) {
      nodeList.push(node);      
  if (nodeList.length > 1) {
        bfs(node.nextElementSibling, nodeList); //搜索当前元素的下一个兄弟元素
      }
      node = nodeList[i++];
      bfs(node.firstElementChild, nodeList); //该层元素节点遍历完了，去找下一层的节点遍历
    }    return nodeList;
}

Algorithme de dérivation de fonctions d'ordre élevé

1. La déduplication du filtre

le filtre est également une opération couramment utilisée. Filtrez certains éléments du tableau et renvoyez les éléments restants. Cela peut également être compris de cette manière. La fonction de rappel du filtre traite chaque élément du tableau. Si le résultat du traitement renvoie faux, le résultat du filtre supprimera l'élément, et s'il est vrai, il restera

Utiliser. la fonction d'ordre supérieur filter(). La clé est qu'elle réside dans l'implémentation correcte d'une fonction "filtre".

En fait, cette fonction de filtrage a plusieurs paramètres, filter(function (element, index, self)), qui démontre l'utilisation de filter pour supprimer les doublons, comme ceci :

var r,
arr = ['apple', 'strawberry', 'banana', 'pear', 'apple', 'orange', 'orange', 'strawberry'];
r = arr.filter(function (element, index, self) {   
     return self.indexOf(element) === index;        
 //拿到元素，判断他在数组里第一次出现的位置，是不是和当前位置一样，
 //一样的话返回true，不一样说明重复了，返回false。
});

2. Algorithme de tri

排序也是在程序中经常用到的算法。无论使用冒泡排序还是快速排序，排序的核心是比较两个元素的大小。如果是数字，我们可以直接比较，但如果是字符串或者两个对象呢？

直接比较数学上的大小是没有意义的，因此，比较的过程必须通过函数抽象出来。通常规定，对于两个元素x和y，如果认为x y，则返回1，这样，排序算法就不用关心具体的比较过程，而是根据比较结果直接排序。

值得注意的例子：

// 看上去正常的结果:
['Google', 'Apple', 'Microsoft'].sort(); // ['Apple', 'Google', 'Microsoft'];
// apple排在了最后:
['Google', 'apple', 'Microsoft'].sort(); // ['Google', 'Microsoft", 'apple']
// 无法理解的结果:
[10, 20, 1, 2].sort(); // [1, 10, 2, 20]

解释原因

第二个排序把apple排在了最后，是因为字符串根据ASCII码进行排序，而小写字母a的ASCII码在大写字母之后。

第三个排序结果，简单的数字排序都能错。

这是因为Array的sort()方法默认把所有元素先转换为String再排序，结果’10’排在了’2’的前面，因为字符’1’比字符’2’的ASCII码小。

因此我们把结合这个原理：

var arr = [10, 20, 1, 2];
    arr.sort(function (x, y) {    
    if (x < y) {        
        return -1;
        }    
            if (x > y) {         
               return 1;
        }        return 0;
    });   
     console.log(arr); // [1, 2, 10, 20]

上面的代码解读一下：传入x，y，如果xy，返回-1，x后面排，如果x=y，无所谓谁排谁前面。

还有一个，sort()方法会直接对Array进行修改，它返回的结果仍是当前Array，一个例子：

var a1 = ['B', 'A', 'C'];var a2 = a1.sort();
    a1; // ['A', 'B', 'C']
    a2; // ['A', 'B', 'C']
    a1 === a2; // true, a1和a2是同一对象

相关免费学习推荐：js视频教程

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!