Maison  >  Article  >  interface Web  >  Plusieurs codes de tri JS courants sur le front-end

Plusieurs codes de tri JS courants sur le front-end

jacklove
jackloveoriginal
2018-05-07 09:17:232156parcourir

Nous rencontrons souvent des problèmes de tri lors de l'utilisation de js. Cet article expliquera en détail le problème de tri de js.

1. Tri à bulles

function bubbleSort(arr){
  var i = 0,
      j = 0;
  for(i=1; i<arr.length; i++){
    for(j=0; j<=arr.length-i; j++){
      var temp = 0;
      // ">" 从小到大排序
      // "<" 从大到小排序
      if(arr[j] > arr[j+1]){
        temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
  return arr;
}

2. Tri rapide

function quickSort(arr,l,r){
  if(l < r){
    var i = l, j = r, x = arr[i];
    while(i<j){
      while(i<j && arr[j]>x)
        j--;
      
      if(i<j)
        //这里用i++,被换过来的必然比x小,赋值后直接让i自加,不用再比较,可以提高效率
        arr[i++] = arr[j];
      
      while(i<j && arr[i]<x)
        i++;
      
      if(i<j)
        //这里用j--,被换过来的必然比x大,赋值后直接让j自减,不用再比较,可以提高效率
        arr[j--] = arr[i];
    }
    arr[i] = x;
    
    quickSort(arr, l, i-1);
    quickSort(arr, i+1, r);
  }
}

3. Fusion bidirectionnelle

function merge(left, right) {
    var result = [],
        il = 0,
        ir = 0;
    while (il < left.length && ir < right.length) {
        if (left[il] < right[ir]) {
            result.push(left[il++]);
        } else {
            result.push(right[ir++]);
        }
    }
    while(left[il]){
        result.push(left[il++]);
    }
    while(right[ir]){
        result.push(right[ir++]);
    }
    return result;
}

Opération de chaîne

1. 🎜>

1. Déterminez la chaîne palindrome
function palindrome(str){
  // \W匹配任何非单词字符。等价于“[^A-Za-z0-9_]”。
  var re = /[\W_]/g;
  // 将字符串变成小写字符,并干掉除字母数字外的字符
  var lowRegStr = str.toLowerCase().replace(re,&#39;&#39;);
  // 如果字符串lowRegStr的length长度为0时,字符串即是palindrome
  if(lowRegStr.length===0) return true;
  // 如果字符串的第一个和最后一个字符不相同,那么字符串就不是palindrome
  if(lowRegStr[0]!=lowRegStr[lowRegStr.length-1]) return false;
  //递归
  return palindrome(lowRegStr.slice(1,lowRegStr.length-1));
}

2. Retournez la chaîne
思路一:反向遍历字符串
function reverseString(str){  
  var tmp = &#39;&#39;;  
   for(var i=str.length-1; i>=0; i--)    
   tmp += str[i];  
   return tmp
 }

Idée 2 : Convertir en opération de tableau
function reverseString(str){
  var arr = str.split("");
  var i = 0,j = arr.length-1;
  while(i<j){
    tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
    i++;
    j--;
  }
  return arr.join("");
}

3. Générez une chaîne aléatoire de longueur spécifiée
function randomString(n){
  var str = &#39;abcdefghijklmnopqrstuvwxyz0123456789&#39;;
  var tmp = &#39;&#39;;
  for(var i=0; i<n; i++) {
    tmp += str.charAt(Math.round(Math.random()*str.length));
  }
  return tmp;
}

4. Comptez les lettres les plus fréquentes dans la chaîne
function findMaxDuplicateChar(str) {
  if(str.length == 1) {
    return str;
  }
  var charObj = {};
  for(var i = 0; i < str.length; i++) {
    if(!charObj[str.charAt(i)]) {
      charObj[str.charAt(i)] = 1;
    } else {
      charObj[str.charAt(i)] += 1;
    }
  }
  var maxChar = &#39;&#39;,
      maxValue = 1;
  for(var k in charObj) {
    if(charObj[k] >= maxValue) {
      maxChar = k;
      maxValue = charObj[k];
    }
  }
  return maxChar + &#39;:&#39; + maxValue;
}

Opération de tableau

1. 🎜>
function unique(arr){
  var obj = {}
  var result = []
  for(var i in arr){
    if(!obj[arr[i]]){
      obj[arr[i]] = true;
      result.push(arr[i]);
    }
  }
  return result;
}

2. Différence maximale dans le tableau

function getMaxProfit(arr){
  var min = arr[0],
      max = arr[0];
  for(var i = 0; i < arr.length; i++){
    if(arr[i] < min) min = arr[i];
    if(arr[i] > max) max = arr[i];
  }
  return max - min;
}

Autres algorithmes courants

1. >

Implémentation récursive

function factorialize(num) {
  var result = 1;
    if(num < 0) return -1;
    if(num == 0 || num == 1) return 1;
    while(num>1) {
      result *= num--;
    }
    return result;
}
2. Générer une séquence de Fibonacci

Forcer l'implémentation récursive
function factorialize(num) {
  var result = 1;
  if(num < 0) return -1;
  if(num == 0 || num == 1) return 1;
  if(num > 1) return num*factorialize(num-1);
}

Implémentation simple non récursive

function getfib(n){
  if(n == 0) return 0;
  if(n == 1) return 1;
  if(n > 1) return getfib(n-1) + getfib(n-2);
}
function fibo(len){
    var fibo = [];
    for(var i = 0; i < len; i++){
      fibo.push(getfib(i));
    }
    return fibo;
}
3. Recherche binaire

Implémentation non récursive
function getFibonacci(n) {
  var fibarr = [];
  var i = 0;
  while(i < n) {
    if(i <= 1) {
      fibarr.push(i);
    } else {
      fibarr.push(fibarr[i - 1] + fibarr[i - 2])
    }
    i++;
  }
  return fibarr;
}

Implémentation récursive

function binary_search(arr, key) {
  var low = 0,
      high = arr.length - 1;
  while(low <= high){
    var mid = parseInt((high + low) / 2);
    if(key == arr[mid]){
      return mid;
    }else if(key > arr[mid]){
      low = mid + 1;
    }else if(key < arr[mid]){
      high = mid -1;
    }
  }
  return -1;
}
Cet article montre plusieurs codes de tri js en détail si vous le souhaitez. Pour en savoir plus, veuillez prêter attention au site Web chinois php.

Recommandations associées :
function binary_search2(arr, low, high, key) {
  if(low > high) return -1;
  var mid = parseInt((low + high)/2);
  if(key == arr[mid]) {
    return mid;
  } else if(key > arr[mid]) {
    return binary_search2(arr, mid+1, high, key);
  } else if(key < arr[mid]) {
    return binary_search2(arr, low, mid-1, key);
  }
}

6 algorithmes de tri JS couramment utilisés et comparaison

Résumé de l'algorithme de tri JS

Analyse de deux algorithmes de tri js pratiques

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!

Déclaration:
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