JavaScript経典の並べ替えアルゴリズム——数え方の並べ替え
842 ワード
カウント順序の中心は、入力されたデータ値をキーに変換して、追加のオープンされた配列空間に格納することである.線形時間複雑度の並べ替えとして、カウント順序は入力されるデータが決定範囲の整数である必要があります.つまり、配列記録配列下の要素を遍歴して何度も出現したことがあります.そして、この要素を位置を探して先に配置します.簡単な点では、元の配列の各要素の値を新しい配列の下付きとしています.
動画ショー:
JavaScriptコードの実現:
動画ショー:
JavaScriptコードの実現:
function countingSort(arr, maxValue) {
var bucket = new Array(maxValue+1),
sortedIndex = 0;
arrLen = arr.length,
bucketLen = maxValue + 1;
for (var i = 0; i < arrLen; i++) {
if (!bucket[arr[i]]) {
bucket[arr[i]] = 0;
}
bucket[arr[i]]++;
}
for (var j = 0; j < bucketLen; j++) {
while(bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}
var arr = [2, 3, 8, 7, 1, 2, 7, 3];
console.log(countingSort(arr,8));//1,2,2,3,3,7,7,8