JavaScript で一般的に使用されるいくつかの並べ替えアルゴリズムを説明する例-フロントエンドQ&A-php.cn

JavaScript で一般的に使用されるいくつかの並べ替えアルゴリズムを説明する例

PHPz

リリース： 2023-04-25 10:04:43

オリジナル

495 人が閲覧しました

JavaScript は、Web ページ上で対話性を作成するために使用される人気のあるプログラミング言語です。並べ替えはコンピューターサイエンスの重要なアルゴリズムの 1 つであり、JavaScript での並べ替えも習得する必要があるスキルです。この記事では、JavaScript で一般的に使用されるいくつかの並べ替えアルゴリズムとその実装方法を紹介します。

バブルソート

バブルソートは、シンプルで直感的な並べ替えアルゴリズムです。その基本的な考え方は、毎回 2 つの隣接する要素を比較し、順序が間違っている場合は位置を交換することです。各ラウンドのソートの後、最大の要素が配列の最後に移動されます。このプロセスは、配列全体がソートされるまで繰り返されます。

次は、バブルソートの JavaScript 実装です:

function bubbleSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len; i++) {
    for (var j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

ログイン後にコピー

上記のコードでは、ネストされたループを使用して、隣接する要素を順番に比較します。現在の要素が次の要素より大きい場合、彼らの位置を交換します。ループの各反復で、最大の要素が配列の最後に移動されます。このアルゴリズムの時間計算量は O(n^2) です。

選択ソート

選択ソートは、もう 1 つの単純な並べ替えアルゴリズムです。その基本的な考え方は、毎回配列内の最小の要素を選択し、それを配列の最後の桁に入れることです。ソートされたシーケンス。選択ソートの時間計算量も O(n^2) です。

以下は選択ソートの JavaScript 実装です:

function selectionSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len - 1; i++) {
    var minIndex = i;
    for (var j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      var temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
  return arr;
}

ログイン後にコピー

上記のコードでは、2 つのネストされたループを使用して最小値を見つけ、それをソートされた配列の末尾に入れ替えます。

挿入ソート

挿入ソートは、シンプルですが効率的な並べ替えアルゴリズムです。その基本的な考え方は、並べ替えられる要素を、既に並べ替えられている要素に順番に挿入することです。順序なしシーケンスの場合、常に最初の要素から開始し、左から右に 1 つの要素を取り出し、それを順序付きシーケンスの適切な位置に挿入します。すべての要素がフェッチされるまで、ソートプロセスは完了します。

以下は挿入ソートの JavaScript 実装です:

function insertionSort(arr) {
  var len = arr.length;
  var current, j;
  for (var i = 1; i < len; i++) {
    current = arr[i];
    j = i - 1;
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
  return arr;
}

ログイン後にコピー

上記のコードでは、while ループを使用してソートされた要素を右に移動し、新しい要素を挿入するためのスペースを確保します。。このアルゴリズムの時間計算量は O(n^2) です。

クイックソート

クイックソートは、一般的に使用される効率的な並べ替えアルゴリズムです。基本的な考え方は、基数を選択し、シーケンス内のすべての数値をこの基数と比較することです。基数より小さい数値を基数の左側に、基数より大きい数値を基数の右側に配置し、左右の部分列を再帰的に処理します。

以下は、クイックソートの JavaScript 実装です:

function quickSort(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));
}

ログイン後にコピー

上記のコードでは、最初にベンチマーク番号を選択し、次にシーケンス全体を走査し、ベンチマーク番号より小さい番号を入力します。基数より大きい数値を別の配列に入れます。最後に、左と右の配列を再帰的に処理し、基数と結合します。このアルゴリズムの時間計算量は O(nlogn) です。

概要

この記事では、いくつかの一般的な並べ替えアルゴリズムと JavaScript でのその実装について紹介します。バブルソート、選択ソート、挿入ソートのいずれであっても、それらはすべて非常に基本的で理解しやすい並べ替えアルゴリズムであり、初心者が学び理解するのに適しています。ソートアルゴリズムについてより深く包括的に学習している場合は、マージソートやヒープソートなどの高度なソートアルゴリズムを使用してみることもできます。

以上がJavaScript で一般的に使用されるいくつかの並べ替えアルゴリズムを説明する例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。