Einfache Implementierung mehrerer Sortieralgorithmen in JavaScript_Grundkenntnisse

Implementierung des Sortieralgorithmus

Meine JS-Kenntnisse sind schlecht, daher verwende ich eine Methode ähnlich wie JAVA und C, um den JavaScript-Sortieralgorithmus zu schreiben.

Und ich werde hier nicht über das Algorithmus-Prinzip sprechen, sondern nur über die Code-Implementierung. Es kann zu Fehlern kommen. Jeder ist herzlich eingeladen, im Blog einen Kommentar zur Orientierung abzugeben.
Einfügesortierung

Die Algorithmusbeschreibung von Insertion-Sort ist ein einfacher und intuitiver Sortieralgorithmus. Es funktioniert, indem es eine geordnete Sequenz erstellt. Bei unsortierten Daten scannt es die sortierte Sequenz von hinten nach vorne, findet die entsprechende Position und fügt sie ein. Bei der Implementierung der Einfügungssortierung wird normalerweise die In-Place-Sortierung verwendet (d. h. eine Sortierung, die nur O(1) zusätzlichen Platz beansprucht). Daher ist es während des Scanvorgangs erforderlich, die Sortierung wiederholt und schrittweise zu verschieben Sortiert Elemente rückwärts und bietet Platz zum Einfügen für das neueste Element.

Der Implementierungscode lautet wie folgt:

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;
}

Zeitkomplexität ist: O(n^2)

Natürlich gibt es Raum für eine Optimierung dieses Algorithmus, beispielsweise durch die Änderung des Positionsalgorithmus für Suche und Ersetzung in eine binäre Suche.
Blasensortierung

Klassischer Sortieralgorithmus, mir bricht das Herz, wenn es um die Blasensortierung geht. Als Student schrieb ich eine Pflichtarbeit über die Verbesserung des Blasensortierungsalgorithmus. Daher konnte ich den Blasensortierungsalgorithmus nach Abschluss der Arbeit nicht vollständig implementieren.

  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;
}

Die Zeitkomplexität beträgt: O(n^2)
Schnellsortierung

Ein sehr klassischer Sortieralgorithmus. Der Sortiervorgang ist hauptsächlich in drei Schritte unterteilt:

1. Wählen Sie ein Element aus der Sequenz aus, das als „Pivot“ bezeichnet wird
Ordnen Sie die Reihenfolge neu an, sodass alle Elemente, die kleiner als der Grundlinienwert sind, vor der Grundlinie platziert werden und alle Elemente, die größer als der Grundlinienwert sind, hinter der Grundlinie platziert werden (die gleiche Zahl kann auf beiden Seiten platziert werden). Nachdem diese Partition beendet wurde, befindet sich die Basis in der Mitte der Sequenz. Dies wird als Partitionsvorgang bezeichnet
2. Sortieren Sie rekursiv das Subarray der Elemente, die kleiner als der Basiswert sind, und das Subarray der Elemente, die größer als der Basiswert sind.
Der Implementierungscode lautet wie folgt:

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;
}

Die Zeitkomplexität beträgt: O(nlogn).

Sortierung zusammenführen
Es ist auch ein sehr klassischer Sortieralgorithmus. Ich habe die Gelegenheit genutzt, js zu lernen, um den klassischen Sortieralgorithmus zu überprüfen. Ideen zur Zusammenführungssortierung finden Sie in meinem Blog: Zusammenführungssortierung. Ich schreibe hier nur die js-Implementierung.

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];
  }
}

Beim Schreiben der Zusammenführungssortierung gab es noch eine kleine Episode: js konnte nicht automatisch aufrunden, daher habe ich später die parseInt-Methode verwendet, was sehr süß war.