選択ソートアルゴリズムのJavaScript実装の分析例（写真）-jsチュートリアル-php.cn

選択ソートアルゴリズムのJavaScript実装の分析例（写真）

黄舟

リリース： 2017-04-15 09:31:36

オリジナル

1860 人が閲覧しました

この記事では、主に JavaScript によって実装された選択ソートアルゴリズムを紹介し、サンプルの形で選択ソートの原理、実装手順、および関連する操作テクニックを分析します。この記事では、JavaScript 選択ソートアルゴリズムの実装について説明しています。参考のために皆さんと共有してください。詳細は次のとおりです:

単純選択ソート

は最もよく知られた比較方法です。そのアルゴリズムのアイデアは次のとおりです: 配列の先頭から開始して、最初のものを比較します。要素を他の要素と比較します。すべての要素がチェックされた後、最小の要素が配列の最初の位置に配置され、アルゴリズムは 2 番目の位置から続行されます。このプロセスは、配列の最後から 2 番目の位置に到達するまで継続され、すべてのデータが並べ替えられます。コードは次のとおりです:

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>JavaScript选择排序</title>
</head>
<body>
<script type="text/javascript">
 function selectSort(nums){//选择排序
  var min;//最小值
  for(var outer=0;outer<nums.length-1;outer++){//外循环选中元素
   min=outer;
   for(var inner=outer+1;inner<=nums.length;++inner){
    if(nums[inner]<nums[min]){//如果内循环中元素比选中元素小
     min=inner;//将其标为最小元素
    }//直到每次外循环的最小元素
    swap(nums,outer,min);//最小值被调整到合适的位置
   }
  }
 }
 function swap(arr,i,j){//交换位置
  var temp=arr[i];
  arr[i]=arr[j];
  arr[j]=temp;
 }
 function show(nums){//显示数组
  for(var i=0;i<nums.length;i++){
   document.write(nums[i]+&#39; &#39;);
  }
  document.write(&#39;<br>&#39;);
 }
 var nums=[6,8,0,6,7,4,3,5,5,10];
 show(nums);//6 8 0 6 7 4 3 5 5 10
 selectSort(nums);
 show(nums);//0 3 4 5 5 6 6 7 9 10
</script>
</body>
</html>

ログイン後にコピー

分析によると、単純な選択ソートの時間計算量は

O(n2)

です。選択並べ替えの主な操作はキーワード間の比較であるため、単純な選択並べ替えを改善するには、比較を減らす方法から始める必要があります。実際、現実世界にもゲームの総合優勝という好例があります。 8 人の中からチャンピオンを選ぶには、実際には 7+6+5=18 ゲーム必要ではなく、ペアで比較することができ、つまり 11 ゲームです。この方法は

ツリー選択ソートと呼ばれます。 ツリー選択ソート

は、トーナメントの考え方に基づいた選択ソートの方法です。まず、n個のレコードのキーワードをペアごとに比較し、その中からn/2個の小さいものを比較します。最小のキーワードを見つけます。これは完全な二分木で表すことができます。n 個のノードを含む完全な二分木の深さは log2n+1 であるため、サブスモールキーワードの各選択はソートプロセス中に log2n 操作のみを必要とするため、その時間計算量は

O です。 (nlog2n ) ただし、この並べ替えには多くのスペースが必要になるという欠点があります。

そこで、より優れたソート、ヒープソート

を導入する必要があります。

添付:

ヒープソートアルゴリズムヒープソート

必要なレコードサイズの補助スペースは1つだけであり、ソートされる各レコードは1つのストレージスペースのみを占有します。

ヒープのソートは、大きなルートヒープ (または小さなルートヒープ) の先頭に記録されたキーが最大 (または最小) であるという機能を利用し、最大 (または最小) のキーワードを持つレコードを選択するのが簡単になります。現在の未注文の領域にあります。大きなヒープを例に挙げてみましょう。ソートの基本的な操作は次のとおりです:

まず、ヒープを構築します。ヒープの構築は、len2 から始まり、最初のノードまで継続して行われます。ここで、len はヒープの数です。ヒープを構築するプロセスは線形プロセスであり、ヒープを調整するプロセスは常に len2 から 0 まで呼び出されます。ヒープの構築の時間計算量は O(n) です。

次のステップは、

調整ヒープ

です。調整ヒープは、ヒープの構築とヒープの並べ替えのプロセスで使用されます。その目的は、ノード i とその子ノード left(i) と
right(i) を比較することです。 3 つのうちの最大 (または最小) の値がノード i ではなく、その子ノードの 1 つである場合は、2 つのノードを交換して、再帰を続行します。その後、ヒープソート: ヒープのルートノードを削除し、ルートノードを最後の要素に置き換え、最初のlen-1ノードでヒープ調整プロセスを続行し、すべてのノードが削除されるまでルートノードを削除します。。
ヒープ調整の時間計算量はO(log2n)したがって、ヒープソートの時間計算量はO(nlog2n)です。ヒープソートはインプレースソートであり、その補助スペースは O(1) です。ただし、不安定です (ソートの安定性とは、ソートされたシーケンス内に 2 つの同一の要素がある場合、それらの相対位置がソートの前後で変わらないことを意味します)。以下は、ヒープを構築するプロセスをシミュレートします:

ヒープのソートは、レコード数が少ないファイルに対して推奨する価値はありませんが、n が大きいファイルに対しては依然として非常に効果的です。