JavaScript: ソートアルゴリズムとコード実装のトップ 10

この記事の内容には、(双方向) バブル ソート、選択ソート、挿入ソート、クイック ソート (穴埋めとスワッピング)、マージ ソート、バケット ソート、基数ソート、カウンティング ソート (最適化)、ヒープ ソート、シェル ソートが含まれます。ここでコードをテストできます。 LeetCode のその他の JavaScript ソリューションは、私のアルゴリズム リポジトリにも掲載されていますので、ぜひご覧ください。

また、トップ 10 ランキングの C++ バージョンも添付します。JavaScript に慣れているため、C++ バージョンは少し見苦しいですが、気にしないでください。

役に立つと思ったら、励みになるように星を付けてください。ありがとうございます😊

まず、さまざまなアルゴリズムのアニメーションデモンストレーションを表示するために使用できる、データ構造とアルゴリズムの動的視覚化ツールをお勧めします。本文は以下から始まります。

バブルソート

隣接する要素を比較して交換することにより、各ループは順序付けられていない配列の最高値または最低値を見つけることができます。

***: O(n)、配列は 1 つのバブルのみの後にソートされます。

最悪の場合: O(n²)

平均: O(n²)

一方向バブリング

関数 bubbleSort(nums) {  
  for( i = 0 、 len = nums .length; i < len-1 ; i++) {  
    // 比較のラウンドで交換する必要のあるデータがない場合、配列はすでに順序付けられていることを意味します。主に[5,1,2,3,4]のような配列を最適化します 
    mark = trueとします。  
    for( j = 0 ; j < len-i-1 ; j++) {  
      数値[j] >数値[j+1]の場合 
        [nums[j], nums[j+1]] = [nums[j+1], nums[j]];  
マーク= false ;  
      }  
    }  
    if(マーク) return;  
  }  
 }

双方向バブリング

通常のバブル ソートでは、1 サイクルで最大値または最小値しか見つけられませんが、双方向バブル ソートでは最大値と最小値の両方を見つけるのにさらに 1 サイクルかかります。

関数 bubbleSort_twoWays(数値) {  
  low = 0とします。  
  high = nums.length - 1 とします。  
  低い<  高い） {  
    mark = trueとします。  
    // *** 値を見つけて右側に置きます 
    for( i = low ; i < high ; i++) {  
      数値[i] >数値[i+1]の場合 
        [nums[i], nums[i+1]] = [nums[i+1], nums[i]];  
マーク= false ;  
      }  
    }  
    高い - ;  
    // 最小値を見つけて左に配置する 
    for( j = high ; j > low; j--) {  
      if(nums[j] <  数字[j-1]）{  
        [nums[j], nums[j-1]] = [nums[j-1], nums[j]];  
マーク= false ;  
      }  
    }  
    低++;  
    if(マーク) return;  
  }  
 }

選択ソート

バブルソートと似ていますが、選択ソートでは各要素をその後の要素と比較して交換するという点が異なります。

***: O(n²)

最悪の場合: O(n²)

平均: O(n²)

関数 selectSort(nums) {  
  for( i = 0 、 len = nums .length; i < len ; i++) {  
    for( j = i +1; j < len ; j++) {  
      if(nums[i] > nums[j]) {  
        [nums[i], nums[j]] = [nums[j], nums[i]];  
      }  
    }  
  }  
 }

挿入ソート

最初の要素は順序付けられた配列として使用され、後続の要素はこの順序付けられた配列内の適切な位置を見つけることによって挿入されます。

***: O(n)、元の配列はすでに昇順になっています。

最悪の場合: O(n²)

平均: O(n²)

関数 insertSort(nums) {  
  for( i = 1 、 len = nums .length; i < len ; i++) {  
    temp = nums [i]とします。  
    j = iとします。  
    j > = 0 && temp <の間 数字[j-1]）{  
      数値[j] = 数値[j-1];  
      j--;  
    }  
    数値[j] = temp;  
  }  
 }

クイックソート

要素を基数 (通常は最初の要素) として選択し、基数より小さい要素をその左側に、基数より大きい要素を右側に配置し (バイナリ検索に相当)、基数の両側のシーケンスを再帰的に繰り返します。

***: O(n * logn)、すべての数字は底の両側に均等に分布します。このときの再帰は、左右のシーケンスを連続的に2つに分割することです。

最悪の場合: O(n²)、すべての数値は基数の片側に分散され、左と右のシーケンスを分割することは挿入ソートと同等です。

平均: O(n * log n)

参考学習リンク:

アルゴリズム3: 最もよく使われるソート - クイックソート

3種類のクイックソートとクイックソート最適化

迅速な選別ピット​​充填

右から中央に進むと、基数より小さい数値は左側（最初は基数の位置）に割り当てられ、右側は元の値を保持し、後で左側の値が埋められます。

関数 quickSort(数値) {  
  // ベースの両側のシーケンスを再帰的にソートする 
  関数再帰(arr, left, right) {  
    if(左> = 右) 戻り値:  
    index =パーティション(arr, left, right) とします。  
    再帰(arr, 左, インデックス - 1);  
    再帰(arr, インデックス + 1, 右);  
    arr を返します。  
  }  
  // 底より小さい数を底の左側に置き、底より大きい数を底の右側に置き、底の位置を返します 
  関数パーティション(arr, left, right) {  
    // *** 数を基数として取る 
    temp = arr [左]とします。  
    while(左<  右） {  
      while(左<  右&& arr[右] > = temp) 右--;  
      arr[左] = arr[右];  
      while(左<  右&& arr[左] <   temp ) 左++;  
      arr[右] = arr[左];  
    }  
    //ベースの位置を変更する 
    arr[左] = 一時;  
    左に戻る;  
  }  
  再帰(nums, 0, nums.length-1);  
 }

クイックソートスワップ

左右から真ん中へ移動する際に、一致しない数字に遭遇した場合は、両側の値を入れ替えます。

関数 quickSort1(数値) {  
  関数再帰(arr, left, right) {  
    if(左> = 右) 戻り値:  
    index =パーティション(arr, left, right) とします。  
    再帰(arr, 左, インデックス - 1);  
    再帰(arr, インデックス + 1, 右);  
    arr を返します。  
  }  
  関数パーティション(arr, left, right) {  
    temp = arr [左]とします。  
    p =左+ 1 とします。  
    q = rightとします。  
    p < = q の場合 
      p < = q && arr[p] <の間  temp ) p++;  
      p < = q && arr[q] > temp の間、q--;  
      p < = qの場合{  
        [arr[p], arr[q]] = [arr[q], arr[p]];  
        // 値を入れ替えた後、それぞれの側は中央に向かって1つずつ移動します 
        p++;  
        q--;  
      }  
    }  
    //ベースの位置を変更する 
    [arr[左], arr[q]] = [arr[q], arr[左]];  
    q を返します。  
  }  
  再帰(nums, 0, nums.length-1);  
 }

マージソート

配列を再帰的に 2 つのシーケンスに分割し、2 つのシーケンスを順番にマージします。

***: O(n * logn)

最悪の場合: O(n * logn)

平均: O(n * log n)

参考学習リンク:

グラフィカルソートアルゴリズム（IV） - マージソート

関数 mergeSort(nums) {  
  // 2つの配列を順番にマージする 
  関数マージ(l1, r1, l2, r2) {  
    arr = [] とします。  
    インデックスを0にします。  
    i = l1 、 j = l2とします。  
    i < = r1 && j < = r2 の間 
      arr[インデックス++] = nums[i] <   nums [j] ? nums[i++] : nums[j++];  
    }  
    i < = r1 の場合、 arr[index++] = nums[i++];  
    j < = r2 の場合、arr[index++] = nums[j++];  
    // 順序付けされたマージされた配列を元の配列に戻します 
    for( t = 0 ; t <インデックス; t++) {  
      nums[l1 + t] = arr[t];  
    }  
  }  
  // 配列を再帰的に2つのシーケンスに分割します 
  関数再帰(左、右) {  
    if(左> = 右) 戻り値:  
    // (left+right)/2 と比較すると、数値オーバーフローを回避するために次の記述が推奨されます。  
    mid = parseInt ((right - left) / 2) + left とします。  
    再帰(左、中央);  
    再帰(中央+1、右);  
    マージ(左、中央、中央+1、右);  
    数値を返します。  
  }  
  再帰(0, 数値の長さ-1);  
 }

バケットソート

n 個のバケットを取り、配列の最大値と最小値に応じて各バケットに格納される数値の間隔を決定し、配列要素を対応するバケットに挿入し、最後にバケットをマージします。

***: O(n)、各数字はバケットに分散されるため、数字をバケットに挿入してソートする必要はありません (スペースと時間を交換してソートをカウントするのと同様)。

最悪の場合: O(n²)、すべての数字が 1 つのバケットに分散されます。

平均: O(n + k)、ここで k はバケットの数です。

参考学習リンク:

面接でバケットソートについて質問しないでください。 ！ ！

関数bucketSort(nums) {  
  // バケットの数（正の数）  
  num = 5とします。  
  max = Math .max(...nums);とします。  
  min = Math.min (...nums);とします。  
  // 各バケットの値の範囲を計算します。少なくとも 1 である必要があります。  
  range = Math .ceil((max - min) / num) || 1 とします。  
  // 2 次元配列を作成します。最初の次元はバケットの数を表し、2 番目の次元はバケットに格納されているバイト数を表します。  
  arr = Array.from (Array(num)).map(() = > Array().fill(0));とします。  
  nums.forEach( val = > {  
    //要素をどのバケットに分配するかを計算する 
    index = parseInt ((val - min) / range);とします。  
    // インデックスが範囲外にならないようにします。たとえば、[5,1,1,2,0,0] の場合、インデックスは 5 として表示されます。  
インデックスインデックス= インデックス> = num ? num - 1 : インデックス;  
    temp = arr [インデックス]とします。  
    // 挿入ソート、要素を順番にバケットに挿入する 
    j = temp .length - 1 とします。  
    j > = 0 && val <の間 温度[j]) {  
      temp[j+1] = temp[j];  
      j--;  
    }  
    temp[j+1] = val;  
  })  
  // 元の配列に戻す 
  res = [].concat.apply([], arr);とします。  
  nums.forEach((val, i) = > {  
    nums[i] = res[i];  
  })  
 }

基数ソート

0～9 の 10 個のバケットを使用し、桁数に応じて各数字を下位から上位まで対応するバケットに入れ、最大値の桁数を循環させます。ただし、負の符号や小数点の比較はできないため、並べられるのは正の整数のみです。

***: O(n * k)、ここで k は *** 値の桁数を表します。

最悪の場合: O(n * k)

平均: O(n * k)

参考学習リンク:

アルゴリズム概要シリーズ 5: 基数ソート

関数 radixSort(nums) {  
  // 桁数を計算する 
  関数 getDigits(n) {  
    合計を0とします。  
    while(n) {  
      合計++;  
 n = parseInt (n/10);  
    }  
    合計を返します。  
  }  
  // 最初の次元は桁数（0～9）を表し、2 番目の次元はそこに格納される値を表します。  
  arr = Array.from (Array(10)).map(() = > Array());とします。  
  max = Math .max(...nums);とします。  
  maxDigits = getDigits (max);とします。  
  for(let i = 0 , len = nums .length; i < len ; i++) {  
    // 各数字を同じ桁数まで 0 で埋める 
    nums[i] = (nums[i] + '').padStart(maxDigits, 0);  
    // まず各数字を1桁ずつ対応するバケットに入れます 
    temp = nums [i][nums[i].length-1]とします。  
    arr[temp].push(nums[i]);  
  }  
  // 各桁を決定するためにループする 
  for(let i = maxDigits -2; i > =0; i--) {  
    // 各バケットをループする 
    ( j = 0 ; j < = 9; j++ の場合) {  
      temp = arr [j]とします 
      len = temp .length;とします。  
      // 現在の桁 i に応じて、バケット内の数字を対応するバケットに格納します。  
      while(len--) {  
        str = temp [0]とします。  
        temp.shift();  
        arr[str[i]].push(str);  
      }  
    }  
  }  
  // 元の配列に戻す 
  res = [].concat.apply([], arr);とします。  
  nums.forEach((val, インデックス) = > {  
    nums[インデックス] = +res[インデックス];  
  })  
 }

カウントソート

配列要素の値をキーとして、出現回数を値として使用して一時配列に格納し、この一時配列を走査して元の配列に復元します。 JavaScript 配列の添え字は文字列として保存されるため、カウントソートは負の数のソートには使用できますが、小数のソートには使用できません。

***: O(n + k)、kは最大値と最小値の差です。

最悪の場合: O(n + k)

平均: O(n + k)

関数 countingSort(nums) {  
  arr = [] とします。  
  max = Math .max(...nums);とします。  
  min = Math.min (...nums);とします。  
  // バケット 
  for(let i = 0 , len = nums .length; i < len ; i++) {  
    temp = nums [i]とします。  
    arr[温度] = arr[温度] + 1 || 1;  
  }  
  インデックスを0にします。  
  // 元の配列を復元する 
  for( i = min ; i < = max; i++) {  
    (arr[i] > 0) の間 {  
      nums[インデックス++] = i;  
      arr[i]--;  
    }  
  }  
 }

カウントソートの最適化

特殊なケースでスペースの無駄を避けるために、各配列要素に min の逆数を追加します。この最適化により、解放されるスペースのサイズを max+1 から max-min+1 に減らすことができます。ここで、max と min はそれぞれ配列内の最大値と最小値です。

たとえば、配列[103、102、101、100]の場合、通常のカウントソートでは長さ104の配列を開く必要があり、最初の100の値は未定義です。この最適化方法を使用した後は、長さ4の配列のみを開くことができます。

関数 countingSort(nums) {  
  arr = [] とします。  
  max = Math .max(...nums);とします。  
  min = Math.min (...nums);とします。  
  // 最小値の反対を追加して配列の範囲を狭めます 
  add = -min とします。  
  for(let i = 0 , len = nums .length; i < len ; i++) {  
    temp = nums [i]とします。  
    temp += 追加;  
    arr[温度] = arr[温度] + 1 || 1;  
  }  
  インデックスを0にします。  
  for( i = min ; i < = max; i++) {  
    temp = arr [i+add]とします。  
    温度が0以上である間 
      nums[インデックス++] = i;  
      温度--;  
    }  
  }  
 }

ヒープソート

配列に基づいてヒープ (完全なバイナリ ツリーに類似) を作成します。各ノードの値は、左と右のノードよりも大きくなります (最大ヒープ、通常は昇順で使用されます)。または、左と右のノードよりも小さくなります (最小ヒープ、通常は降順で使用されます)。昇順ソートの場合、最初に *** ヒープを作成し、次に最上位の要素 (*** 値を表す) と最下位の要素を交換します。各交換で、順序付けられていないシーケンスの *** 値を取得できます。ヒープを並べ替え、最上位の要素と最下位の要素を交換し、これを n-1 回繰り返して昇順の配列を取得します。

***: O(n * logn)、logn は *** ヒープ調整にかかる時間です。

最悪の場合: O(n * logn)

平均: O(n * log n)

参考学習リンク:

一般的なソートアルゴリズム - ヒープソート

グラフィカルソートアルゴリズム（III）ヒープソート

関数 heapSort(nums) {  
  // インデックスの値が左ノードと右ノードより大きくなるように***ヒープを調整します 
  関数adjustHeap(数値、インデックス、サイズ) {  
    // スワップ後、ヒープ構造が破壊される可能性があります。各親ノードが左右のノードよりも大きくなるようにループする必要があります。  
    while(true) {  
      max =インデックスとします。  
      let left = index * 2 + 1; // 左ノード 
      let right = index * 2 + 2; // 右ノード 
      if(左<  サイズ&& 数値[最大] <   nums [左]) max =左;  
      if(右<  サイズ&& 数値[最大] <   nums [右]) max =右;  
      // 左と右のノードが現在のノードよりも大きい場合は、それらを交換して再度ループし、交換後の左と右のノードの位置がヒープ構造を破壊するかどうか（左と右のノードよりも小さいかどうか）を判断します。  
      if(インデックス !== 最大値) {  
        [nums[インデックス], nums[最大]] = [nums[最大], nums[インデックス]];  
インデックス=最大;  
      }  
      それ以外 {  
        壊す;  
      }  
    }  
  }  
  //*** ヒープを構築する 
  関数buildHeap(nums) {  
    // ここでのヘッドノードは 0 から始まるので、最後の非リーフノードは parseInt(nums.length/2)-1 になることに注意してください。  
    start = parseInt (nums.length / 2) - 1 とします。  
    size = nums.lengthとします。  
    // 最後の非リーフノードからヒープの先頭まで調整を開始します。  
    for(let i = start ; i > =0; i--) {  
      ヒープを調整します(数値、i、サイズ);  
    }  
  }  
  ヒープを構築します(数値);  
  // n-1 回ループし、各ループの後にヒープの最上位要素と最下位要素を入れ替えてヒープ構造を再調整します。  
  for(let i = nums.length -1; i > 0; i--) {  
    [nums[i], nums[0]] = [nums[0], nums[i]];  
    ヒープを調整します(数値、0、i);  
  }  
 }

シェルソート

シーケンス全体は、一定の増分ギャップを介していくつかのグループに分割され、グループ内のメンバーが後ろから前に向かって比較および交換され、その後、増分は徐々に 1 に減少します。シェルソートは挿入ソートに似ていますが、開始時の前進ステップ数が 1 からギャップに変更される点が異なります。

***: O(n * logn)、ステップ サイズは常に半分になります。

最悪の場合: O(n * logn)

平均: O(n * log n)

参考学習リンク:

グラフィカルソートアルゴリズム（II） - シェルソート

関数shellSort(nums) {  
  len = nums.lengthとします。  
  // 初期ステップ数 
  ギャップをparseInt (len/2)とします。  
  // 徐々にステップ数を減らす 
  while(ギャップ) {  
    // ギャップ要素からトラバースを開始する 
    for( i = gap ; i < len ; i++) {  
      // 徐々に他のグループメンバーと比較し、交換する 
      for( j = i -gap; j > =0; j- = gap ) {  
        if(nums[j] > nums[j+gap]) {  
          [nums[j], nums[j+gap]] = [nums[j+gap], nums[j]];  
        }  
        それ以外 {  
          壊す;  
        }  
      }  
    }  
ギャップ= parseInt (ギャップ / 2);  
  }  
 }

これを読んで何か質問があったり、間違いを見つけたりした場合は、下にメッセージを残すか、私のリポジトリに問題を提起して一緒に議論することができます😊