Maison > Article > interface Web > Résumé de l'algorithme de tri JS
Cette fois, je vais vous apporter un résumé de l'algorithme de tri JS. Quelles sont les précautions lors de l'utilisation de l'algorithme de tri JS. Voici des cas pratiques, jetons un coup d'œil.
On peut trouver beaucoup de questions sur les algorithmes de tri sur Internet, mais la version JS pure est relativement dispersée, je l'ai spécialement triée lors de l'entretien précédent, avec une comparaison de l'efficacité du tri
1.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.
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. 🎜>4. Tri par colline
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; };5. Tri par fusion
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; };6. Tri rapide
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)); }Comparaison de l'efficacité de l'algorithme --- ----------------------------------------------- --- ----------
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)); };| Algorithme de tri | Cas moyen | Meilleur cas | Pire cas |
---------------- --------------------------------------------------
| Tri à bulles | O(n²) | O(n) | Stable |----------------------- --- -----------------------------------------------
| Tri de sélection | O(n²) | O(n²) | Instable|
----------------------- ----------- --------------------------------
| Tri des insertions | O(n²) | O(n) | O(n²) |
----------------------------- --------------- ------------------
| Tri par colline | O(nlogn)~O(n²) | O(n^1,5) | O(n²) | Non stable|
-------------------------------- ---------------- ------------------
| Tri de fusion | O(nlogn) | | O(nlogn) | Stable |
----- ---------------------------------- ---------------- --------
| Tri rapide | O(nlogn) | O(n²) | >------------- ------------------------------------ --------------
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 php. Site chinois !
Lecture recommandée :
Comment choisir la version jQuery
Explication détaillée des trois types de $() dans jQuery
Problème d'écriture du titre H5
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!