JSソートアルゴリズムのヒル順序付けと高速ソートの実現方法
本論文の例は、JS順序付けアルゴリズムのヒル順序付けと高速順序付けの実現方法を述べている。皆さんに参考にしてあげます。具体的には以下の通りです。
ヒルの並べ替え:
5、3、1のような間隔のシーケンスを定義します。第1回目の処理では、全間隔5の処理が行われ、次の処理間隔は3の処理が行われ、最後の処理間隔は1の要素となります。つまり、隣接する要素は標準的な挿入順序を実行します。
最後の処理を開始する時、ほとんどの要素は正しい位置にあります。アルゴリズムは多くの元素を交換する必要がなく、これは元素を挿入するより高級なところです。
時間複雑度O(n*logn)
再帰的にデータを小さい要素と大きな要素を含む異なるサブシーケンスに順次分解して、このステップを繰り返して、すべてのデータが秩序化されるまで。
基準値より小さいものを一つの配列に入れます。基準値より大きいのは配列の中に入れます。
時間複雑度O(n*logn)
PS:ここでは並べ替えに関するデモンストレーションを紹介します。
オンラインアニメーションのデモ挿入/選択/発泡/帰結/ヒル/高速ソートアルゴリズムプロセスツール:
http://tools.jb51.net/aideddesign/paixu_システム
もっと多くのJavaScriptに関する内容に興味がある読者は、当駅のテーマを見ることができます。「JavaScript数学演算の使い方のまとめ」、「JavaScriptデータ構造とアルゴリズム技術のまとめ」、「JavaScript配列操作技術のまとめ」、「JavaScriptソートアルゴリズムのまとめ」、「JavaScriptはアルゴリズムと技術の総括を遍歴します。」、「JavaScript検索アルゴリズムのテクニックのまとめ」および「JavaScriptエラーとデバッグテクニックのまとめ」
本論文で述べたように、JavaScriptプログラムの設計に役に立ちます。
ヒルの並べ替え:
5、3、1のような間隔のシーケンスを定義します。第1回目の処理では、全間隔5の処理が行われ、次の処理間隔は3の処理が行われ、最後の処理間隔は1の要素となります。つまり、隣接する要素は標準的な挿入順序を実行します。
最後の処理を開始する時、ほとんどの要素は正しい位置にあります。アルゴリズムは多くの元素を交換する必要がなく、これは元素を挿入するより高級なところです。
時間複雑度O(n*logn)
function shellSort(){
var N=arr.length;
var h=1;
while(h<N/3){
h=3*h+1;//
}
while(h>=1){
for(var i=h; i<N; i++){
for(j=i; j>=h && arr[j]<arr[j-h]; j-=h){
swap(arr, j, j-h);
}
}
h=(h-1)/3;
}
}
function swap(array, i, j){//
var temp =array[j];
array[j]=array[i];
array[i]=temp;
}
クイックソート:再帰的にデータを小さい要素と大きな要素を含む異なるサブシーケンスに順次分解して、このステップを繰り返して、すべてのデータが秩序化されるまで。
基準値より小さいものを一つの配列に入れます。基準値より大きいのは配列の中に入れます。
時間複雑度O(n*logn)
function quickSort(arr){
if(arr.length==0){
return [];
}
var left=[];
var right=[];
var p=arr[0];
for(var i=1; i<arr.length; i++){
if(arr[i]<p){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
return quickSort(left).concat(p,quickSort(right));
}
高速並べ替えは、大規模なデータセットに適しており、小さいデータセットを扱うと、逆に性能が低下します。PS:ここでは並べ替えに関するデモンストレーションを紹介します。
オンラインアニメーションのデモ挿入/選択/発泡/帰結/ヒル/高速ソートアルゴリズムプロセスツール:
http://tools.jb51.net/aideddesign/paixu_システム
もっと多くのJavaScriptに関する内容に興味がある読者は、当駅のテーマを見ることができます。「JavaScript数学演算の使い方のまとめ」、「JavaScriptデータ構造とアルゴリズム技術のまとめ」、「JavaScript配列操作技術のまとめ」、「JavaScriptソートアルゴリズムのまとめ」、「JavaScriptはアルゴリズムと技術の総括を遍歴します。」、「JavaScript検索アルゴリズムのテクニックのまとめ」および「JavaScriptエラーとデバッグテクニックのまとめ」
本論文で述べたように、JavaScriptプログラムの設計に役に立ちます。