Six algorithmes de tri JS couramment utilisés et comparaison

Cette fois, je vais vous présenter les 6 algorithmes de tri JS couramment utilisés et leur comparaison. Quelles sont les précautions lors de l'utilisation de l'algorithme de tri JS. Voici des cas pratiques, jetons un coup d'œil.

1.Tri à bulles

var bubbleSort = function(arr) {
  for (var i = 0, len = arr.length; i < len - 1; i++) {
    for (var j = i + 1; j < len; j++) {
      if (arr[i] > arr[j]) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
};

2.Tri par sélection

var selectSort = function(arr) {
  var min;
  for (var i = 0; i < arr.length - 1; i++) {
    min = i;
    for (var j = i + 1; j < arr.length; j++) {
      if (arr[min] > arr[j]) {
        min = j;
      }
    }
    if (i != min) {
      swap(arr, i, min);
    }
    console.log(i + 1, ": " + arr);
  }
  return arr;
};
function swap(arr, index1, index2) {
  var temp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = temp;
};

3. >

var insertSort = function(arr) {
  var len = arr.length,
    key;
  for (var i = 1; i < len; i++) {
    var j = i;
    key = arr[j];
    while (--j > -1) {
      if (arr[j] > key) {
        arr[j + 1] = arr[j];
      } else {
        break;
      }
    }
    arr[j + 1] = key;
  }
  return arr;
};

4. Tri par colline

function shellSort(arr) {
  if (arr.length < 2) {
    return arr;
  };
  var n = arr.length;
  for (gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap /= 2)) {
    for (i = gap; i < n; ++i) {
      for (j = i - gap; j >= 0 && arr[j + gap] < arr[j]; j -= gap) {
        temp = arr[j];
        arr[j] = arr[j + gap];
        arr[j + gap] = temp;
      }
    }
  }
  return arr;
};

5. Tri par fusion

function merge(left, right) {
  var result = [];
  while (left.length > 0 && right.length > 0) {
    if (left[0] < right[0]) {
      // shift()方法用于把数组的第一个元素从其中删除，并返回第一个元素的值
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  return result.concat(left).concat(right);
}
function mergeSort(arr) {
  if (arr.length == 1) {
    return arr;
  }
  var middle = Math.floor(arr.length / 2),
    left = arr.slice(0, middle),
    right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

6. Tri rapide

var quickSort = function(arr) {　　
  if (arr.length <= 1) {
    return arr;
  }
  var pivotIndex = Math.floor(arr.length / 2);　
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];　　
  for (var i = 0; i < arr.length; i++) {　　　
    if (arr[i] < pivot) {　　　　　　
      left.push(arr[i]);　　　　
    } else {　　　　　　
      right.push(arr[i]);　　　　
    }　
  }　　
  return quickSort(left).concat([pivot], quickSort(right));
};

Efficacité de l'algorithme Comparer

4. 🎜>

------------------------------------------------------------ --- --------------------
| Algorithme de tri | Cas moyen | Meilleur cas | Pire cas |
------ -------------------------------------------------- -------
| Tri à bulles | O(n²) | O(n²) | Stable |
------------- --- ------------------------------------
| Tri de sélection | (n²) | O(n²) | Instable|
--------------- ---------- -----------------------------
| Tri par insertion | O(n²) | | Stable |
---------------------------------- ---------- ----------------------
| Tri par colline | O(nlogn)~O(n²) | | Instable|
--------------------------------- ---------- ------------------
| Tri de fusion | O(nlogn) | O(nlogn) | Stable |
----- ------------------------------------------------ ------- -----------
| Tri rapide | O(nlogn) | O(n²) | Instable|
-------- ------------------------------------------ -------- -

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

Lecture recommandée :

Implémentation JS de l'analyse des étapes de la barre de progression dynamique

Le chargement paresseux de vue-router résout le premier problème lent vitesse de chargement Explication détaillée des étapes

Explication détaillée des étapes de déploiement nginx du projet vue.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!