ホームページ >ウェブフロントエンド >jsチュートリアル >選択ソートアルゴリズムのJavaScript実装の分析例（写真）
選択ソートアルゴリズムのJavaScript実装の分析例（写真）
- 黄舟オリジナル
- 2017-04-15 09:31:361914ブラウズ
この記事では、主に 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]+' ');
}
document.write('<br>');
}
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 が大きいファイルに対しては依然として非常に効果的です。
以上が選択ソートアルゴリズムのJavaScript実装の分析例（写真）の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。