Maison  >  Article  >  interface Web  >  Organiser les algorithmes de tri JS couramment utilisés

Organiser les algorithmes de tri JS couramment utilisés

php中世界最好的语言
php中世界最好的语言original
2018-05-26 15:36:081140parcourir

Cette fois, je vais vous présenter quelques algorithmes de tri JS couramment utilisés. Quelles sont les précautions à prendre pour utiliser les algorithmes 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. 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²) | 🎜>----------------------- --------------- -------------------
| Tri par insertion | O(n²) | O(n² ) |
---- --------------------------------------------- ----- ---------------
| Tri de colline| O(nlogn)~O(n²) | O(n^1.5) | ------------------------------------------------- - -----------------
| 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 :

Comment utiliser Sortable dans Vue

Comment utiliser js+css pour obtenir un effet de frappe


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