Implémentation simple de plusieurs algorithmes de tri en JavaScript_Basic knowledge

Mise en place d'un algorithme de tri

Mes compétences en JS sont faibles, j'utilise donc une méthode similaire à JAVA et C pour écrire l'algorithme de tri JavaScript.

Et je ne parlerai pas ici du principe de l'algorithme, juste de l'implémentation du code, il peut y avoir des bugs, tout le monde est invité à commenter sur le blog pour obtenir des conseils.
Tri par insertion

La description de l'algorithme d'Insertion-Sort est un algorithme de tri simple et intuitif. Il fonctionne en construisant une séquence ordonnée. Pour les données non triées, il parcourt la séquence triée d'avant en arrière, trouve la position correspondante et l'insère. Dans la mise en œuvre du tri par insertion, le tri sur place est généralement utilisé (c'est-à-dire un tri qui n'utilise que l'espace supplémentaire O(1). Par conséquent, pendant le processus de numérisation d'arrière en avant, il est nécessaire de décaler de manière répétée et progressive le tri par insertion. éléments triés vers l'arrière, fournissant un espace d'insertion pour le dernier élément.

Le code d'implémentation est le suivant :

function insertSort(arr) {
  if (!arr) return;
  var len = arr.length;
  if (len == 0 || len == 1) return;

  for (var i = 1, len = arr.length; i < len; i ++) {
    var stand = arr[i];
    for (var j = i - 1; j >= 0; j --) {
      if (arr[j] > stand) {
        arr[j + 1] = arr[j];
      } else {
        arr[j + 1] = stand;
        break;
      }
    }
  }

  return arr;
}

La complexité temporelle est : O(n^2)

Bien sûr, il est possible d'optimiser cet algorithme, comme changer l'algorithme positionnel de recherche et le remplacer par une recherche binaire.
Tri à bulles

Algorithme de tri classique, j'ai le cœur brisé quand il s'agit de tri à bulles. Quand j'étais étudiant, j'ai rédigé une thèse obligatoire sur l'amélioration de l'algorithme de tri à bulles. En conséquence, je n'ai pas pu mettre en œuvre pleinement l'algorithme de tri à bulles après avoir fini d'écrire la thèse.

  if (!arr) return;
  var len = arr.length;
  if (len == 0 || len == 1) return;

  for (var i = 0; i < len; i ++) {
    for (var j = 0; j < len - i - 1; j ++) {
      if (arr[j] > arr[j + 1]) {
        var tmp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = tmp;
      }
    }
  }

  return arr;
}

La complexité temporelle est : O(n^2)
Tri rapide

Un algorithme de tri très classique. Le processus de tri se divise principalement en trois étapes :

1. Choisissez un élément de la séquence, appelé le « pivot »
 ;
2. Réorganisez la séquence de sorte que tous les éléments plus petits que la valeur de base soient placés devant la ligne de base et que tous les éléments plus grands que la valeur de base soient placés derrière la ligne de base (le même nombre peut être placé de chaque côté). Une fois cette partition terminée, la base se trouve au milieu de la séquence. C'est ce qu'on appelle une opération de partition
3. Triez récursivement le sous-tableau d'éléments plus petits que la valeur de base et le sous-tableau d'éléments supérieurs à la valeur de base.

Le code d'implémentation est le suivant :

function quickSort(arr, bt, ed) {
  if (bt < ed) {
    var pivot = findPartition(arr, bt, ed);
    quickSort(arr, bt, pivot - 1);
    quickSort(arr, pivot + 1, ed);
  }
}

function findPartition(arr, bt, ed) {
  var stand = arr[bt];

  while (bt < ed) {
    while (bt < ed && arr[ed] >= stand) {
      ed --;
    }
    if (bt < ed) {
      arr[bt ++] = arr[ed];
    }
    while (bt < ed && arr[bt] <= stand) {
      bt ++;
    }
    if (bt < ed) {
      arr[ed --] = arr[bt]; 
    }
  }

  arr[bt] = stand;
  return bt;
}

La complexité temporelle est : O(nlogn).
Tri par fusion

C'est aussi un algorithme de tri très classique. J'ai profité de l'apprentissage du js pour revoir l'algorithme de tri classique. Pour des idées sur le tri par fusion, vous pouvez vous référer à mon blog : Merge Sort. J'écris uniquement l'implémentation js ici.

function mergeSort(arr, bt, ed) {
  if (bt < ed) {
    var mid = bt + parseInt((ed - bt) / 2);
    mergeSort(arr, bt, mid);
    mergeSort(arr, mid + 1, ed);
    mergeArray(arr, bt, mid, ed);    
  }
}

function mergeArray(arr, bt, mid, ed) {
  var mArr = [];
  var i = bt, j = mid + 1;
  while (i <= mid && j <= ed) {
    if (arr[i] <= arr[j]) {
      mArr.push(arr[i++]);
    } else {
      mArr.push(arr[j ++]);
    }
  }

  if (i <= mid) {
    mArr = mArr.concat(arr.slice(i, mid + 1));
  }

  if (j <= ed) {
    mArr = mArr.concat(arr.slice(j, ed + 1));
  }

  for (var h = 0; h < mArr.length; h ++) {
    arr[bt + h] = mArr[h];
  }
}

Il y a eu un autre petit épisode lors de l'écriture du tri par fusion : js ne pouvait pas arrondir automatiquement, j'ai donc utilisé plus tard la méthode parseInt, qui était très mignonne.