JavaScriptでのバケットソートの詳しい説明

この記事では、JavaScript でのバケットの並べ替えについて説明します。JavaScript でのバケットの並べ替えについて知らない場合、または JavaScript でのバケットの並べ替えに興味がある場合は、この記事を見てみましょう。 point

バケットソートはカウンティングソートのバージョンアップ版です。 関数 のマッピング関係を利用します。効率の鍵はこのマッピング関数の決定にあります。

バケットの並べ替えをより効率的にするには、次の 2 つのことを行う必要があります:

1. 十分な追加スペースがある場合は、バケットの数を増やすようにしてください。

2.入力 N を変換します。データは K 個のバケットに均等に分散されます

同時に、バケット内の要素の並べ替えでは、どの比較並べ替えアルゴリズムを選択するかがパフォーマンスに重大な影響を与えます。

いつが最も速いか

入力データが各バケットに均等に分散できる場合

最も遅いのはい​​つか

入力データが同じバケットに分散される場合

バケット並べ替え JavaScript コードの実装:

function bucketSort(arr, bucketSize) {  
    if (arr.length === 0) {  
      return arr;  
    }  
  
    var i;  
    var minValue = arr[0];  
    var maxValue = arr[0];  
    for (i = 1; i < arr.length; i++) {  
      if (arr[i] < minValue) {  
          minValue = arr[i];                //输入数据的最小值  
      } else if (arr[i] > maxValue) {  
          maxValue = arr[i];                //输入数据的最大值  
      }  
    }  
  
    //桶的初始化  
    var DEFAULT_BUCKET_SIZE = 5;            //设置桶的默认数量为5  
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;  
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;     
    var buckets = new Array(bucketCount);  
    for (i = 0; i < buckets.length; i++) {  
        buckets[i] = [];  
    }  
  
    //利用映射函数将数据分配到各个桶中  
    for (i = 0; i < arr.length; i++) {  
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);  
    }  
  
    arr.length = 0;  
    for (i = 0; i < buckets.length; i++) {  
        insertionSort(buckets[i]);                      //对每个桶进行排序，这里使用了插入排序  
        for (var j = 0; j < buckets[i].length; j++) {  
            arr.push(buckets[i][j]);                        
        }  
    }  
  
    return arr;}

上記がこの記事のすべての内容です。あまり詳しくない場合は、両方を自分で実装することができ、簡単に習得できるでしょう。

関連する推奨事項:
バケットソートアルゴリズムの PHP 実装例の共有

以上がJavaScriptでのバケットソートの詳しい説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。