Javascript ソート アルゴリズム カウント ソート example_javascript スキル

カウンティングソートは安定したソートアルゴリズムです。カウント ソートでは追加の配列 Count_arr を使用します。ここで、i 番目の要素は、ソートされる配列 Arr 内の値が i に等しい要素の数です。次に、配列 Count_arr に従って、Arr 内の要素を正しい位置に配置します。
は 4 つのステップに分かれています。
1. 並べ替える配列内の最大要素と最小要素を検索します。
2. 配列内の値 i を持つ各要素の出現数をカウントし、それを配列 Count_arr 項目 i
3. すべてのカウントを累積します (Count_arr の最初の要素から開始して、各項目を前の項目に追加します)
4. 元の配列を逆にたどります: 各要素 i を Count_arr に追加します。新しい配列の (i) 番目の項目を取得し、要素ごとに Count_arr(i) を 1 減算します

例:

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

/**
* カウンティングソートは、非比較ベースのソートアルゴリズムです。
* このアルゴリズムは、1954 年に Harold H. Seward によって提案されました。
* その利点は、特定の範囲内の整数をソートするときに、
* その複雑さは Ο(n k) (k は整数の範囲)、
* どの比較ソート アルゴリズムよりも高速であることです。
*
*/

function countSort(arr, min, max) {
var i , z = 0、count = [];

for (i = min; i count[i] = 0;
}

for (i=0; i count[arr[i]] ;
}

for (i = min; i while (count[i]-- > 0) {
arr[z ] = i;
}
}
return arr;
}

// test

var i, arr = [];

for (i = 0; i arr.push(Math.floor ( Math.random() * (141)));
}

countSort(arr, 0, 140);