JavaScript_javascript スキルの並べ替えアルゴリズム コード

ソートの基準となるデータ項目を「ソートコード」といい、データ要素のキーコードとなります。検索を容易にするために、通常、コンピュータ内のデータ テーブルがキー コードによって順序付けされていることが望まれます。たとえば、順序付きリストでの半分の検索は、検索効率が高くなります。また、バイナリ ソート ツリー、B ツリー、および B ツリーの構築プロセスはソート プロセスです。キーが主キーの場合、ソート後の順序は一意になりますが、キーが二次キーの場合、ソート結果は一意ではない可能性があります。これは、同じキーを持つデータ要素が同じであるためです。ソート結果では、これらの要素間の位置関係がソート前と同じには保たれなくなります。
一連のデータ要素に対して特定のソート方法が使用されている場合、キーによってソートされます。同じキーを持つ要素間の位置関係がソート前後で一貫している場合、このソート方法は安定していると言われます ;A一貫性を保てないソート方法を不安定と呼びます。
ソートは、内部ソートと外部ソートの 2 つのカテゴリに分類されます。
内部ソート: ソート対象の列が完全にメモリに格納されるソート プロセスを指し、大きすぎない要素シーケンスに適しています。
外部ソート: ソート処理中に外部メモリにアクセスする必要があることを指します。十分な大きさの要素シーケンスを完全にメモリに入れることができないため、外部ソートのみを使用できます。

次に、3 つの並べ替えアルゴリズムの JavaScript 実装を投稿します。

1 つ目は最も単純な、誰もが知っているバブルソートです。あまり言う必要はありません。コードを貼り付けてください

コードをコピー コードは次のとおりです:

/** @name バブルソート
* @lastmodify 2010/07/13
* @desc 比較ソート
複雑さは O(n*n)
*/
function BubbleSort(list){
var len = list.length;
var cl,temp;
while(len--){
cl = list.length ;
while(cl--){
if(list[cl]>list[len] && cl < len){
temp = list[len]; list[len] = list[cl];
list[cl] = temp;
}
}

}


それでは最後の共通クイックソートは基本的に面接で聞かれます。

コードをコピー コードは次のとおりです:

/**@name クイックソート

* @lastmodify 2010/07/14
* @desc 比較ソート
最悪の実行時間 O(n*n)
最良の実行時間 O(nlogn)
*/
関数 QuickSort(list){
var j = list.length;
var left;
var k = findK (i , j);
if(k != 0){
var leftArr = [];
varmidArr = [リスト[k]] ;
while(len--) {
if(len != k){
if(list[len] > list[k]){
rightArr.push(list[len] );
}
else{
leftArr.push(list[len])
}
}
left = QuickSort(leftArr); = QuickSort( rightArr);
list = left.concat(midArr).concat(right);
}
}

関数 findK(i,j) {
//デフォルトで中間位置を検索します
return Math.floor((i j) / 2);
}


クイックソートの主なアイデアは次のとおりです。分割統治法 (ソート対象) シーケンスが 2 つのブロックに分割されるため、ソートの複雑さが軽減されます。再帰の賢い使い方は、クイック ソートの巧妙さでもあります。前の例では、最初に findK 関数を使用して「参照要素」を見つけ、次に他の要素をこの要素と順番に比較し、それより大きい要素はすべて 1 つのセットに入れられ、それより小さい要素は別のセットに入れられます。 2 つのコレクションを並べ替えます。クイック ソートの効率は主に、findK 関数の実装とソートされる要素の順序に依存します。したがって、クイックソートは不安定な並べ替えアルゴリズムです。

しかし、クイック ソートは依然として比較ベースの並べ替えアルゴリズムです。すべての比較ベースの並べ替えアルゴリズムの特徴の 1 つは、どんなに最適化されていても、要素のセットの平均並べ替え時間は、セット内の要素の数が増加するにつれて常に増加することです。非比較ソートは、この欠点をうまく克服し、ソート時間の複雑さを数値に関係なく安定した値にしようとします。代表的なものはバケットソートです。まず JavaScript の実装を見てみましょう。




コードをコピー

コードは次のとおりです:

/**@name バケットソート
* @author lebron
* @lastmodify 2010/07/15
* @desc 非比較ソート
*/
function BucketSort(list) {
var len = list.length;
var range = findMax(list); [],
count = [];
var i,j;
for (i = 0; i < range; i ) {
count.push(0);

for ( j = 0; j count[list[j]] ;
result.push(0);
for ( i = 1; i < i ) {
count[i] = count[i-1] count[i];
for (j = len - 1; j >= 0; j--) {
結果[リスト[j]]] = リスト[j]
}
結果を返します。 🎜>}

function findMax(list) {
return MAX;
}


ご覧のとおり、バケット ソートの実装では、findMax は依然として大きな配列の範囲を決定するために使用される関数ですが、ここでは定数 MAX に直接置き換えられています。まず、長さ MAX の大きな配列カウントを初期化します。たとえば、値が 24 の要素がある場合、count の 24 番目のビットは 1 としてマークされ、結果の配列の長さは 1 になります。次に、count 配列内の 1 とマークされた要素の位置と、count 配列全体内の 1 とマークされた要素の位置を計算します。このとき、count配列のn番目の要素の値がソート後の位置となるはずで、nはソート後のこの位置に対応する値になります。したがって、最後に count 配列のキー値を 1 つずつ結果配列にマッピングします。
バケットのソートは、要素がセット内で n 番目に大きい場合、その要素が n 番目にランク付けされるべきであるという考えを巧みに使用しており、前後の要素がそれより大きいか小さいかは気にしません (その必要はありません)。比較するため）。明らかに、実際の状況では、ソートされたセットの要素の値の範囲はセットの要素の数よりもはるかに大きいため、対応する巨大な領域の配列を割り当てる必要があります。したがって、バケット ソートの一般的なシナリオは外部ソートです。

興味のある学生は、時間のかかる 3 種類の並べ替えを桁違いにテストしてみることができます。