1。バケットソートの紹介
バケットソートは、カウントベースのソートアルゴリズムです。動作の原則は、データを限られた数のバケットに分割することであり、各バケットは個別にソートされます（他のソートアルゴリズムを使用するか、繰り返しの方法でソートを続けることができます）。ソートするデータの値が均等に分布する場合、バケットソート時間の複雑さはθ（n）です。バケットソートはクイックソートとは異なり、比較ソートではなく、時間の複雑さO（NLOGN）の下限の影響を受けません。
バケットソートは、次の4つのステップで実行されます。
（1）固定数の空のバケツを設定します。
（2）データを対応するバケットに入れます。
（3）空白のないバケツのデータを並べ替えます。
（4）結果を得るために、空でないバケツからデータをスプライスします。
バケットソートは、主に小範囲の整数データに適しており、独立して均等に分布しています。計算できるデータの量は大きく、線形予想時間を満たしています。
2。バケットソートアルゴリズムのデモンストレーション
たとえば、現在、一連のデータがあります[7、36、65、56、33、60、110、42、42、94、59、22、83、84、63、77、67、101]。小さいものから大規模に並べ替える方法は？
操作手順：
（1）バケットの数を5つの空のバケツに設定し、最大値110と最小値7を見つけ、各バケットの範囲は20.8 =（110-7+1）/5です。
（2）元のデータを横断し、リンクされたリスト構造で対応するバケットに入れます。数字7、バケットインデックス値は0、計算式は床（（7 7） / 20.8）、番号36、バケットインデックス値は1、計算式フロア（（36 7） / 20.8）です。
（3）同じインデックスで2回目のインデックスでデータをバケットに挿入する場合、バケツに既存の数値と新しく挿入された数値のサイズを決定し、それらを左から右へ、小から大部分に挿入します。たとえば、インデックス2のバケツが挿入されると、63を挿入すると、バケットに56、59、60、および65の数字が既にあり、65の左側に番号63が挿入されます。
（4）非空白のバケツをマージし、左から右に順に0、1、2、3、および4バケツをマージします。
（5）バケットソートの構造を取得します
3。NodeJSプログラムの実装
バケットソートなどの成熟したアルゴリズムを実装することは難しくありません。上記のアイデアによると、私はそれらを実装する簡単なプログラムを書きました。最も厄介な部分は、JavaScriptを使用してリンクリストを操作することだと感じています。
実際のコードは次のとおりです。
'使用 厳しい';//////////////////////////////////////////////////////// ////////////////////////////////////////////////// ////////////////////////////////////////////////// ////////////////////////////////////////////////// ////////////////////////////////////////////////// ////////////////////////////////////////////////// ////////////////////////////////////////////////// //////////////////////////////////////////////////ソート（[1,4,1,5,3,2,3,3,2,5,2,8,9,2,1]、5） * sort（[1,4,1,5,3,3,3,2,5,2,8,9,2,1]、5,0,5）、5,0,5） */exports.sort = function（arr、count）{if（arr.length -= 0）; count = count || （カウント> 1？カウント：10）; //最大値と最小値var min = arr [0]、max = arr [0]; for（var i = 1; i <arr.length; i ++）{min = min <arr [i]？ min：arr [i]; max = max> arr [i]？ max：arr [i]; } var delta =（max -min + 1） / count; // console.log（min+"、"+max+"、"+delta）; // Bucket var Buckets = [];初期化//（var i = 0; i <arr.length; i ++）{var idx = math.floor（（arr [i] - min） /delta）; // Bucket Index if（buckets [idx]）{//空だvar bucket = buckets [idx]; var insert = false; //フラグストーンL.retraversal（bucket、function（item、done）{if（arr [i] <= item.v）{// smaller、insert l.append（item、_val（arr [i]））; insert = true; done（）; // exit traversal}}）; if（！insert）{// than、insert l.append（bucket、_val（arr [i]））; }} else {//空のバケットvar bucket = l.init（）; L.Append（Bucket、_val（arr [i]））;バケット[idx] =バケット; //リンクリスト実装}} var result = []; for（var i = 0、j = 0; i <count; i ++）{l.retraversal（buckets [i]、function（item）{// console.log（i+"："+item.v）; result [j ++] = item.v;}）; } return result;} //リンクリストストレージオブジェクト関数_val（v）{return {v：v}}プログラムを実行します：
var algo = require（ './ index.js'）; var data = [7、36、65、56、33、60、110、42、42、94、59、22、83、84、63、77、67、101]; console.log（data）; console.log（algo.buckett.（data、5）; console.log（algo.bucketsort.sort（data、10））; // 10バケツ
出力：
7、22、33、36、42、42、56、67、67、77、83、84、94、101、110] [7、22、33、36、42、42、56、59、60、63、65、67、77、83、84、94、101、110] 63、65、67、77、83、84、94、101、110] [7、22、33、36、42、42、56、59、60、63、65、67、77、83、84、94、101、110] [7、22、33、36、42、42、56、56、59、63、63、63、63、63、63、63、63、63、63、63、63、63、63、63、63、63、63、63、63、63、63、63、63、63、63、63、63、63、63 84、94、101、110] [7、22、33、36、42、42、56、59、60、63、65、67、77、83、84、94、101、110] [7、22、33、36、42、42、56、59、60、63、65、67、77、83、83、83、83、83、83、83、83、83、83、83、83、83
説明する必要があるのは次のとおりです。
（1）プログラムに記載されているように、挿入プロセス中にバケツのソートを実装できます。または、ソートなしで挿入してから、マージプロセス中にソートすることができ、高速ソートを呼び出すことができます。
（2）リンクリスト。基礎となるノードのAPIには、リンクリストの実装があります。私はそれを直接使用しませんでしたが、リンクリストパッケージを介してそれを呼びました：https：//github.com/nodejs/node-v0.x-archive/blob/master/lib/_linklist.js
4。ケース：大学入学試験のスコアに関するバケットソート統計
バケットソートの最も有名なアプリケーションシナリオの1つは、大学入学試験のスコアをカウントすることです。 1年間の国立大学入学試験候補者の数は900万人で、スコアは標準で、最低200人と最大900人です。10桁はありません。これらの900万個の数字がソートされている場合、私たちは何をすべきですか？
アルゴリズム分析：
（1）比較ベースのソート、クイックソートを使用する場合、平均時間の複雑さはO（nlogn）= o（9000000*log9000000）= 144114616 = 144百万の比較です。
（2）カウントベースのソート、バケットソート、および平均的な複雑さを使用する場合、線形の複雑さを制御できます。 200分から900分のバケツ、O（n）= o（90000000）700バケツを作成する場合、900Wのデータを1回スキャンするのと同等です。
クイックソートとバケットソートを一度に比較するプログラムを実行します。
// [200,900]に100Wのデータを作成する閉じた間隔varデータ= algo.data.randomdata（1000*1000,200,900）; var s1 = new Date（）。バケットvar s3 = new date（）。getTime（）; console.log（ "QuickSort Time：％SMS"、S2-S1）; Console.Log（ "Bucket Time：％SMS"、S3-S2）;
出力：
クイックソート時間：14768msbucket時間：1089ms
したがって、大学入学試験のスコアリングの場合、バケツの並べ替えがより適しています！適切なシナリオで適切なアルゴリズムを使用すると、ハードウェアを超えたプログラムのパフォーマンスの改善がもたらされます。
5。バケットソートコスト分析
しかし...
バケットソートは、関数のマッピング関係を利用して、ほとんどすべての比較作業を減らします。実際、バケットソートのf（k）値の計算は、速い順序で分割と同等であり、大量のデータを基本的に順序付けられたデータブロック（バケット）に分割しています。その後、バケツ内の少量のデータの高度な比較と並べ替えを行う必要があります。
バケットソートNキーワードの時間の複雑さは、2つの部分に分割されます。
（1）各キーワードのバケットマッピング関数を計算するためのループ、そして今回の複雑さはO（n）です。
（2）高度な比較ソートアルゴリズムを使用して、各バケットのすべてのデータを並べ替えて、時間の複雑さを除いて、∑o（ni*logni）。ここで、Niはi番目のバケットのデータ量です。
明らかに、パート（2）はバケットソートのパフォーマンスの決定要因です。バケット内のデータの量を最小化することは、効率を改善する唯一の方法です（比較ソートに基づく最高の平均時間の複雑さは、O（n*logn）にのみ到達できるため）。したがって、次の2つのポイントを実行するために最善を尽くす必要があります。
（1）マッピング関数f（k）は、各バケットに[n/m]データボリュームを持つように、nデータをmバケットに均等に割り当てることができます。
（2）バレルの数を増やすようにしてください。極端な場合、各バケットは1つのデータのみを取得でき、バケット内のデータの「比較」並べ替えを完全に回避できます。もちろん、これを行うのは簡単ではありません。データの量が膨大な場合、F（k）関数はバケットコレクションの数を膨大にし、宇宙廃棄物が深刻になります。これは、時間と空間のコスト間のトレードオフです。
nデータをソートし、mバケツの場合、各バケット[n/m]データの平均バケットソート時間の複雑さは次のとおりです。
o（n）+o（m*（n/m）*log（n/m））= o（n+n*（logn-logm））= o（n+n*logn-n*logm）
n = mの場合、つまり、制限の下でバケットごとにデータが1つしかない場合。バケットソートの最良の効率は、O（n）に達することができます。
6。概要
バケットソートの平均時間の複雑さは線形o（n+c）で、c = n*（logn-logm）です。バレルMの数が同じnに対して大きい場合、その効率が高くなり、最高の時間の複雑さはO（n）に達します。もちろん、バケットソートのスペースの複雑さはO（n+m）です。入力データが非常に大きく、バケットの数が非常に多い場合、スペースコストは間違いなく高くなります。さらに、バケットソートは安定しています。
実際、私は別の感覚を持っています。検索アルゴリズムの中で、比較ベースの検索アルゴリズムの最高の時間の複雑さはO（logn）です。たとえば、ハーフフィニッシュの検索、バランスの取れたバイナリツリー、赤と黒の木など。ただし、ハッシュテーブルにはO（c）線形レベルの検索効率があります（競合がない場合は、検索効率はO（1）に達します）。よく見てみましょう：ハッシュテーブルの考えとバケツの並べ替えは同じ曲ですか？