ホームページ > ウェブフロントエンド > jsチュートリアル > JSでカウントソートを実装する方法

JSでカウントソートを実装する方法

亚连
リリース: 2018-06-22 17:14:58
オリジナル
2034 人が閲覧しました

この記事では、主に JS で実装された計数ソートと基数ソートのアルゴリズムを紹介します。サンプルの形で計数ソートと基数ソートの原理と JS 実装テクニックを簡単に分析します。この記事では、JS Counting ソートおよび基数ソート アルゴリズムの実装について説明しています。詳細は次のとおりです:

カウンティングソートカウンティングソートは、配列内の数値の出現数を表すため、バケットとなります。補助配列は通常、100 未満の範囲でソートするために使用されます。時間計算量は O(n) で、空間計算量は配列の数値範囲です。

/**
 * 范围在 start - end 之间的排序
 * 计数排序需要辅助数组,该辅助数组的长度是待排序数组的范围,所以一般用作范围小于100的排序
 */
function countSort(arr, start, end) {
  var len = arr.length;
  // 桶数组
  var suportArr = new Array(end - start + 1);
  // 结果数组
  var resArr = new Array(len);
  // 初始化桶数组
  for (i = 0; i < suportArr.length; i++) {
    suportArr[i] = 0;
  }
  // 待排序数组中的数组出现,在桶子对应位置+1代表这个数出现的个数+1了
  for (let i = 0; i < len; i++) {
    suportArr[arr[i]]++;
  }
   // 从第1项开始,桶数组加上前一个桶的个数,现在辅助数组的意义变成了每一项的排名了。
  for (let i = 1; i < suportArr.length; i++) {
    suportArr[i] += suportArr[i - 1];
  }
  // 根据辅助数组的排名,从后往前赋值
  for (let i = len - 1; i >= 0; i--) {
    resArr[suportArr[arr[i]] - 1] = arr[i];
    suportArr[arr[i]]--;
  }
  return resArr;
}
ログイン後にコピー

基数ソート基数ソートはマルチレイバケットソートです

var radix = 16; // 基数,可以为任何数,越大趟数越小,但是桶数越多,最好根据最大数字进行定义。
function _roundSort(arr, round, radix) {
  var buckets = new Array(radix);
  for (let i = 0; i < radix; i++) {
    buckets[i] = [];
  }
  // 将数组中的数放进对应的桶子中
  for (let i = 0; i < arr.length; i++) {
    let remainder = Math.floor(arr[i] / (radix ** (round - 1))) % radix;
    buckets[remainder].push(arr[i]);
  }
  // 将数组重新根据桶子进行排序
  var index = 0;
  for (let i = 0; i < buckets.length; i++) {
    for (let j = 0; j < buckets[i].length; j++) {
      arr[index++] = buckets[i][j];
    }
  }
}
function radixSort(arr, round) {
  for (let i = 1; i <= round; i++) {
    _roundSort(arr, i, radix);
  }
  return arr;
}
console.log(radixSort([10,5,5,50,0,155,4622,5,1,4,2154], 4));
ログイン後にコピー

以上は皆さんのためにまとめたもので、今後皆さんのお役に立てれば幸いです。

関連記事:

Mac に nvm をインストールする方法 (詳細なチュートリアル)

WeChat アプレットに time 関数を実装する方法

Webpack で生成されたコードの探索

以上がJSでカウントソートを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
最新の問題
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート