Maison >interface Web >js tutoriel >Implémenter un algorithme de tri en utilisant JS
Cette fois je vais vous présenter l'utilisation de JS pour implémenter l'algorithme de tri, et l'utilisation de JS pour implémenter l'algorithme de tri Quelles sont les précautions Voici un cas pratique, jetons un oeil ? .
Quelques implémentations courantes d'algorithmes de tri js, non originales, utilisées pour l'enregistrement
Complexité temporelle : O(n^2) ;
Le plus rapide : lorsque les données sont dans l'ordre direct
Le plus lent : lorsque les données sont dans l'ordre inverse
function bubbleSort(arr) { var len = arr.length; for (var i = 0; i < len; i++) { for (var j = 0; j < len - 1 - i; i++) { // 相邻元素两两对比,元素交换 if (arr[j] > arr[j + 1]) { var temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp; } } } return arr; }
Complexité temporelle : O (n^2)
L'algorithme de tri le plus stable
function selectionSort(arr) { var len = arr.length; var minIndex, temp; // 寻找最小的数,将索引保存 for (var i = 0; i < len - 1; i++) { minIndex = i; for (var j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } return arr; }
Tri par insertion
Complexité temporelle : O(n^2);
Tri poker
function insertionSort(arr) { var len = arr.length; var preIndex, current; for (var i = 1; i < len; i++) { preIndex = i - 1; current = arr[i]; while (preIndex >= 0 && arr[preIndex] > current) { arr[preIndex + 1] = arr[preIndex]; preIndex--; } arr[preIndex + 1] = current; } return arr; }
Tri par colline
Complexité temporelle : O(n log n);
function shellSort(arr) { var len = arr.length, temp, gap = 1; //动态定义间隔序列 while (gap < len / 3) { gap = gap * 3 + 1; } for (gap; gap > 0; gap = Math.floor(gap / 3)) { for (var i = gap; i < len; i++) { temp = arr[i]; for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) { arr[j + gap] = arr[j]; } arr[j + gap] = temp; } } return arr; }
Tri par fusion
Complexité temporelle : O(n log n) ) ;
function mergeSort(arr) { var len = arr.length; if (len < 2) { return arr; } var middle = Math.floor(len / 2), left = arr.slice(0, middle), right = arr.slice(middle); return merge(mergeSort(left), mergeSort(right)); function merge(left, right) { var result = []; while (left.length && right.length) { if (left[0] <= right[0]) { result.push(left.shift()); } else { result.push(right.shift()); } } while (left.length) result.push(left.shift()); while (right.length) result.push(right.shift()); return result; } }
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 :
Modèle de stratégie de Javascript
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!