上位 10 の古典的なソートアルゴリズムの JS バージョン

序文

読者は自分で試してみることができます。ソースコードはここ (https://github.com/damonare/Sorts) で確認できます。ブロガーは github にライブラリを構築しており、読者はそれをクローンしてローカルで試すことができます。このブログ投稿はソースコードの経験があればもっと良くなる

世の中には、雷鋒と雷峰塔、小平と平頭男、メアリーとマリオ、Javaとjavascriptなど、似ているようで全く違うものが常に存在します...Javaに気に入られるために、javascriptは恥知らずにもJavaの名付け子になりました。ああ、ひざまずいて舐めているべきでしょうか、結局のところ、彼はJavaの姓を名乗っています。しかし現在、JavaScript が復活し、Web 分野をほぼ独占しています。Nodejs と React Native の登場により、JavaScript はバックエンドとモバイル端末の両方で地位を占めるようになりました。ウェブの世界では、

JavaScript は他の追随を許さず、トップの座を獲得しました。

コンピュータアルゴリズムとデータ構造の従来の分野では、ほとんどの専門教科書や書籍のデフォルト言語は Java または C/C++ です。O'REILLY は「JavaScript でのデータ構造とアルゴリズムの記述」という本を出版しましたが、著者が失敗したのか、翻訳者がまったく校正しなかったのかはわかりませんが、この本は小さな誤りでいっぱいで、無限に続く小さな虫の 1 つのようで、口の中に糞が詰まっているような気分になり、吐き出すことも飲み込むこともできません。フロントエンド開発者にとって、特に筆記試験や面接では、アルゴリズムテストは難しくありません（

上位 10 位のソートアルゴリズム、または上位 10 位のソートアルゴリズムと同等の難易度のアルゴリズム

) ですが、これまで JavaScript を使用して実装したことがなく、関連するアルゴリズムの原理を注意深く研究したこともないため、記述に時間の無駄が生じてしまいます。そこで、自分で調べてブログにまとめることにしました。必要な時は自分のブログを見れば良いのです。諺にあるように、人に頼るより自分に頼る方が良いのです(ˉ(∞)ˉ)。

アルゴリズムの起源: 9 世紀にペルシャの数学者によって提案されました。「アル・コワリズミ」とは、下の写真の人物です (重要な数学的要素を提案した人は皆、白い帽子をかぶっているようです)。冗談です。数学の歴史に対するアラブ人の貢献は、今でも賞賛に値します。

[[197157]]

文章

ソートアルゴリズムの説明

（１）ソートの定義：キーワードに従ってオブジェクトのシーケンスをソートすること。

入力: n 個の数値: a1、a2、a3、...、an

出力: n 個の順列: a1'、a2'、a3'、...、an'、ただし a1'

もっと具体的に言うと、背の高い人は後ろに立ち、背の低い人は前に立つように、列になって座り、座席を調整します。

（２）アルゴリズムのメリットを説明するために使われる用語の説明

安定: a が元々 b の前にあり、a=b の場合、ソート後も a は b の前にあります。

不安定: a が元々 b の前にあり、a=b の場合、ソート後に a が b の後に表示されることがあります。

内部ソート: すべてのソート操作はメモリ内で実行されます。

外部ソート: データが大きすぎるため、データはディスク上に配置され、ディスクとメモリ間のデータ転送を通じてソートが実行されます。

時間の複雑さ: アルゴリズムの実行にかかる時間。

空間計算量: プログラムを実行するために必要なメモリの量。

時間と空間の複雑さの詳細については、ここ (http://blog.csdn.net/booirror/article/details/7707551/) をクリックするか、Cheng Jie 著の「Data Structure in Chinese」という非常にわかりやすい本をお読みください。

（３）ソートアルゴリズムの図による概要（インターネットからの画像）：

ソート比較:

画像用語集:

n: データサイズ

k: 「バケット」の数

インプレース: 一定のメモリを占有し、追加のメモリを占有しない

アウトプレース: 追加のメモリを占有します

分類カテゴリ:

1. バブルソート

さて、最初のソートアルゴリズムであるバブルソートの概要を説明しましょう。 C言語を学んだ人なら誰でも理解できると思います。多くの人が最初に接するソートアルゴリズムかもしれません。

（１）アルゴリズムの説明

バブルソートは単純なソートアルゴリズムです。ソートする配列を繰り返し処理し、一度に 2 つの要素を比較して、順序が間違っている場合はそれらを交換します。シーケンスを訪問する作業は、交換が不要になるまで、つまりシーケンスがソートされるまで繰り返されます。このアルゴリズムの名前は、小さな要素が交換を通じてゆっくりとシーケンスの先頭に「浮かんで」いくという事実に由来しています。

（２）アルゴリズムの記述と実装

具体的なアルゴリズムは次のように説明されます。

<1>. 隣接する要素を比較します。最初のものが 2 番目のものより大きい場合は、それらを交換します。
<2> 最初のペアから最後のペアまで、隣接する要素の各ペアに対して同じことを実行し、最後の要素の番号が最大になるようにします。
<3>. 最後の要素を除くすべての要素に対して上記の手順を繰り返します。
<4>. ソートが完了するまで手順1～3を繰り返します。

JavaScript コードの実装:

関数bubbleSort(arr) { 
 
    var len = arr.length; 
 
 (var i = 0; i < len; i++)の場合{ 
 
 (var j = 0; j < len - 1 - i; j++)の場合{ 
 
            if (arr[j] > arr[j+1]) { //隣接する要素をペアで比較する
 
                var temp = arr[j+1]; //要素の交換
 
                arr[j+1] = arr[j]; 
 
                arr[j] =一時; 
 
            } 
 
        } 
 
    } 
 
 arrを返します。 
 
 } 
 
 var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; 
 
 console.log(bubbleSort(arr)); //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

改良されたバブルソート:各ソートの最後の交換の位置を記録するためにランドマーク変数 pos を設定します。 pos 位置以降のレコードは所定の位置にスワップされているため、次のソートでは pos 位置までスキャンするだけで十分です。

改善されたアルゴリズムは次のとおりです。

関数bubbleSort2(arr) { 
 
    console.time ( '改善後の時間のかかるバブルソート' ); 
 
    var i = arr.length-1; // 最初は位置は変更されません
 
    i > 0 の場合
 
        var pos = 0; //各旅行の開始時には、レコードは交換されません
 
 (var j = 0; j < i; j++)の場合
 
            もし (arr[j]> arr[j+1]) { 
 
                pos= j; //交換位置を記録する
 
                var tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp; 
 
            } 
 
        i= pos; //次のソートの準備
 
     } 
 
     console.timeEnd( '時間のかかるバブルソートの改善' ); 
 
 arrを返します。 
 
 } 
 
 var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; 
 
 console.log(bubbleSort2(arr)); //[2、3、4、5、15、19、26、27、36、38、44、46、47、48、50]

従来のバブルソートでは、各ソート操作で最大値または最小値しか見つけることができません。各ソート操作で順方向と逆方向の2ラウンドのバブル処理を実行し、一度に2つの最終値（最大値と最小値）を取得する方法を使用することを検討し、これによりソートパスの数をほぼ半分に削減します。

改善されたアルゴリズムは次のように実装されます。

関数bubbleSort3(arr3) { 
 
    var 下限 = 0; 
 
    var high = arr.length-1; //変数の初期値を設定する
 
    var tmp,j; 
 
    console.time ( '2. 時間のかかるバブルソートの改善' ); 
 
    （低<高）{ 
 
 for (j= low; j< high; ++j) //前方バブリング、攻撃者を見つける
 
            もし (arr[j]> arr[j+1]) { 
 
                tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp; 
 
            } 
 
 --high; // 最大値を変更し、1つ前に移動します  
 
 for (j=high; j>low; --j) // 逆バブリングして、最小のものを見つける  
 
            もし(arr[j]<arr[j-1])であれば{ 
 
                tmp = arr[j]; arr[j]=arr[j-1];arr[j-1]=tmp; 
 
            } 
 
        ++low; // 下限値を変更し、1つ前に戻す
 
    } 
 
    console.timeEnd( '2. 時間のかかるバブルソートの改善' ); 
 
 arr3 を返します。 
 
 } 
 
 var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; 
 
 console.log(bubbleSort3(arr)); //[2、3、4、5、15、19、26、27、36、38、44、46、47、48、50]

3 つの方法の時間比較:

図からわかるように、改良されたバブルソートでは時間の複雑さが大幅に軽減され、処理時間が短縮されます。読者はここをクリックして自分で試してみることができます。ブロガーは GitHub にライブラリを構築しており、読者はそれをクローンしてローカルで試すことができます。このブログ投稿はソースコードの経験があればもっと良くなります~~~

バブルソートのアニメーションのデモンストレーション:

（３）アルゴリズム分析

***ケース: T(n) = O(n)

入力データがすでに正の順序になっている場合 (すでに正の順序になっているので、わざわざ並べ替える必要はありません...)

最悪の場合: T(n) = O(n2)

入力データが逆順の場合（順序を逆にすればいいのに…）

平均ケース: T(n) = O(n2)

2. 選択ソート

最も安定したソートアルゴリズムの 1 つです (この安定性はアルゴリズムレベルの安定性を指すのではありません。2333 さんのおっしゃる意味を理解できるほど賢い方だと思います)。入力されるデータに関係なく、時間の計算量は O(n²) であるためです。したがって、このアルゴリズムを使用する場合は、データサイズが小さいほど良いです。唯一の利点は、余分なメモリスペースを占有しないことです。理論的に言えば、選択ソートはおそらくほとんどの人が思い浮かべる最も一般的なソート方法です。

（１）アルゴリズムの紹介

選択ソートはシンプルで直感的なソートアルゴリズムです。仕組み: まず、ソートされていないシーケンス内の最小 (最大) の要素を見つけて、ソートされたシーケンスの先頭に格納します。次に、残りのソートされていない要素から最小 (最大) の要素を探し、ソートされたシーケンスの最後に配置します。すべての要素がソートされるまでこれを繰り返します。

（２）アルゴリズムの記述と実装

n レコードの直接選択ソートは、n-1 ラウンドの直接選択ソートによって実行され、順序付けられた結果が得られます。具体的なアルゴリズムは次のように説明されます。

<1>. 初期状態: 順序付けされていない領域はR[1..n]であり、順序付けされた領域は空である。
<2>. i番目のソート（i=1,2,3…n-1）が開始されると、現在の順序付き領域と順序なし領域はそれぞれR[1..i-1]とR(i..n)になります。このソートパスは、現在の順序付けられていない領域から最小のキーワードを持つレコード R[k] を選択し、それを順序付けられていない領域の最初のレコード R と交換します。これにより、R[1..i] と R[i+1..n) は、それぞれレコードが 1 つ多い新しい順序付けられた領域と、レコードが 1 つ少ない新しい順序付けられていない領域になります。
<3>. n-1ラウンド後、配列はソートされます。

Javascript コードの実装:

関数selectionSort(arr) { 
 
    var len = arr.length; 
 
    var minIndex、 temp ; 
 
    console.time ( '選択ソート時間' ); 
 
 (var i = 0; i < len - 1; i++)の場合{ 
 
        最小インデックス = i; 
 
 (var j = i + 1; j < len; j++)の場合{ 
 
            if (arr[j] < arr[minIndex]) { //最小の数値を見つける
 
                minIndex = j; //最小数のインデックスを保存する
 
            } 
 
        } 
 
 temp = arr[i]; 
 
        arr[i] = arr[最小インデックス]; 
 
        arr[最小インデックス] = temp ; 
 
    } 
 
    console.timeEnd( '選択ソートに時間がかかります' ); 
 
 arrを返します。 
 
 } 
 
 var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; 
 
 console.log(selectionSort(arr)); //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

選択ソートのアニメーションのデモンストレーション:

（３）アルゴリズム分析

***ケース: T(n) = O(n2)
最悪の場合: T(n) = O(n2)
平均ケース: T(n) = O(n2)

3. 挿入ソート

挿入ソートのコード実装はバブルソートや選択ソートほど単純で粗雑ではありませんが、その原理は最も理解しやすいはずです。ポーカーをプレイしたことがある人なら誰でも数秒で理解できるはずです。もちろん、ポーカーをプレイしているときにカードをランク順に並べることはないと言うのであれば、この人生で挿入ソートアルゴリズムに興味を持つことは決してないと考えられます...

（１）アルゴリズムの紹介

挿入ソートのアルゴリズムの説明は、シンプルで直感的なソートアルゴリズムです。これは、順序付けられたシーケンスを構築することによって機能します。ソートされていないデータの場合は、ソートされたシーケンス内で後ろから前へスキャンし、対応する位置を見つけて挿入します。挿入ソートは通常、インプレースソート（つまり、O(1)の追加スペースのみを必要とするソート）によって実装されます。したがって、後ろから前へスキャンするプロセスでは、挿入する最初の要素のためのスペースを確保するために、ソートされた要素を繰り返し後方に移動する必要があります。

（２）アルゴリズムの記述と実装

一般的に、挿入ソートは配列上でインプレースで実装されます。具体的なアルゴリズムは次のように説明されます。

<1> 最初の要素から始めて、要素はソートされているとみなすことができます。
<2> 次の要素を取り出し、ソートされた要素の順序で後ろから前へスキャンします。
<3>. 要素（すでにソートされている）が新しい要素より大きい場合は、要素を次の位置に移動します。
<4>. ソートされた要素が新しい要素の位置以下になるまで手順3を繰り返します。
<5>. この位置に新しい要素を挿入した後;
<6>. 手順2～5を繰り返します。

Javascript コードの実装:

関数挿入ソート(配列) { 
 
    if (Object.prototype.toString.call(array).slice(8, -1) === '配列' ) { 
 
        console.time ( 'ソート時間を挿入:' ); 
 
 ( var i = 1; i < 配列の長さ; i++) { 
 
            varキー= 配列[i]; 
 
            var j = i - 1; 
 
            while (j >= 0 && 配列[j] >キー) { 
 
                配列[j + 1] = 配列[j]; 
 
                j --;   
 
            } 
 
            配列[j + 1] =キー; 
 
        } 
 
        console.timeEnd( 'ソート時間を挿入:' ); 
 
配列を返します。 
 
    }それ以外{ 
 
戻る  '配列は配列ではありません!' ; 
 
    } 
 
 }

挿入ソートの改善:挿入位置を見つけるときにバイナリ検索を使用する

関数binaryInsertionSort(配列) { 
 
    if (Object.prototype.toString.call(array).slice(8, -1) === '配列' ) { 
 
        console.time ( 'バイナリ挿入ソートには時間がかかります:' ); 
 
 ( var i = 1; i < 配列の長さ; i++) { 
 
            var key = array[i]、左= 0、右= i - 1; 
 
            （左<=右）{ 
 
                var 真ん中 = parseInt((左+右) / 2); 
 
                if (キー< 配列[中央]) { 
 
右= 中央 - 1; 
 
                }それ以外{ 
 
左= 中央 + 1; 
 
                } 
 
            } 
 
 (var j = i - 1; j >=左; j --) {   
 
                配列[j + 1] = 配列[j]; 
 
            } 
 
            配列[左] =キー; 
 
        } 
 
        console.timeEnd( 'バイナリ挿入ソートには時間がかかります:' ); 
 
配列を返します。 
 
    }それ以外{ 
 
戻る  '配列は配列ではありません!' ; 
 
    } 
 
 } 
 
 var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; 
 
 console.log(binaryInsertionSort(arr)); //[2、3、4、5、15、19、26、27、36、38、44、46、47、48、50]

改善前と改善後の比較:

挿入ソートのアニメーションデモンストレーション:

（３）アルゴリズム分析

***ケース: 入力配列は昇順です。 T(n) = O(n)
最悪の場合: 入力配列は降順でソートされます。 T(n) = O(n2)
平均ケース: T(n) = O(n2)

4. シェルソート

1959年にシェル社によって発明されました。

O(n^2) を突破した最初のソートアルゴリズム。単純な挿入ソートの改良版です。挿入ソートとは異なり、より遠い要素の比較を優先します。シェルソートは縮小増分ソートとも呼ばれる

（１）アルゴリズムの紹介

シェルソートの核心は、間隔シーケンスの設定にあります。間隔シーケンスは事前に設定することも、動的に定義することもできます。間隔シーケンスを動的に定義するアルゴリズムは、『アルゴリズム』（第 4 版）の共著者である Robert Sedgewick によって提案されました。

（２）アルゴリズムの記述と実装

まず、ソートするレコードシーケンス全体をいくつかのサブシーケンスに分割し、直接挿入してソートします。具体的なアルゴリズムの説明は次のとおりです。

<1>. 増分シーケンスt1、t2、…、tkを選択します。ここでti>tj、tk=1です。
<2> 増分シーケンスの数kに応じてシーケンスをk回ソートします。
<3> 各ソートラウンドでは、対応する増分tiに従って、ソート対象のシーケンスが長さmの複数のサブシーケンスに分割され、各サブシーケンスに対して直接挿入ソートが実行されます。増分係数が 1 の場合のみ、シーケンス全体がテーブルとして扱われ、テーブルの長さがシーケンス全体の長さになります。

Javascript コードの実装:

関数shellSort(arr) { 
 
    var len = arr.length、 
 
温度、 
 
        ギャップ = 1; 
 
    console.time ( 'シェルのソート時間:' ); 
 
    while(gap < len/5) { //間隔シーケンスを動的に定義する
 
        ギャップ = ギャップ*5+1; 
 
    } 
 
 (ギャップ; ギャップ > 0; ギャップ = Math.floor(gap/5)) { 
 
 ( var i = ギャップ; i < len; i++) { 
 
 temp = arr[i]; 
 
 (var j = i-gap; j >= 0 && arr[j] > temp ; j-=gap)の場合{ 
 
                arr[j+ギャップ] = arr[j]; 
 
            } 
 
            arr[j+ギャップ] = temp ; 
 
        } 
 
    } 
 
    console.timeEnd( 'シェルのソート時間:' ); 
 
 arrを返します。 
 
 } 
 
 var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; 
 
 console.log(shellSort(arr)); //[2、3、4、5、15、19、26、27、36、38、44、46、47、48、50]

ヒルソーティング図（インターネットからの画像）：

（３）アルゴリズム分析

***ケース: T(n) = O(nlog2 n)
最悪の場合: T(n) = O(nlog2 n)
平均的なケース: T(n) = O(nlog n)

5. マージソート

選択ソートと同様に、マージソートのパフォーマンスは入力データの影響を受けませんが、時間の計算量が常に O(n log n) であるため、選択ソートよりもはるかに優れたパフォーマンスを発揮します。コストは、必要な追加のメモリスペースです。

（１）アルゴリズムの紹介

マージソートは、マージ操作に基づいた効果的なソートアルゴリズムです。このアルゴリズムは、分割統治法の非常に典型的な応用です。マージソートは安定したソート方法です。順序付けられたサブシーケンスをマージして、完全に順序付けられたシーケンスを取得します。つまり、最初に各サブシーケンスを順序付けし、次にサブシーケンスのセグメントを順序付けます。 2 つの順序付きリストが 1 つの順序付きリストに結合される場合は、2 方向の結合と呼ばれます。

（２）アルゴリズムの記述と実装

具体的なアルゴリズムは次のように説明されます。

<1>. 長さnの入力シーケンスを長さn/2の2つのサブシーケンスに分割します。
<2>. 2つの部分列をそれぞれマージソートします。
<3> 2 つのソートされたサブシーケンスを最終的なソートされたシーケンスにマージします。

JavaScript コードの実装:

 function mergeSort(arr) { //トップダウン再帰法を使用する
 
    var len = arr.length; 
 
    長さが2以下の場合
 
 arrを返します。 
 
    } 
 
    var middle = Math.floor(len / 2)、 
 
左= arr.slice(0, 中央)、 
 
右= arr.slice(中央); 
 
 merge(mergeSort(左), mergeSort(右))を返します。 
 
 } 
 
関数merge(左,右) 
 
 { 
 
    var 結果 = []; 
 
    console.time ( 'マージソート時間' ); 
 
    while (左.長さ &&右.長さ) { 
 
        （左[0] <=右[0]）の場合{ 
 
            結果.push(左.shift()); 
 
        }それ以外{ 
 
            結果.push(右.shift()); 
 
        } 
 
    } 
 
    while (左.長さ) 
 
        結果.push(左.shift()); 
 
    while (右.長さ) 
 
        結果.push(右.shift()); 
 
    console.timeEnd( 'マージソートには時間がかかります' ); 
 
結果を返します。 
 
 } 
 
 var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; 
 
 console.log(マージソート(arr));

マージソートのアニメーションデモンストレーション:

（３）アルゴリズム分析

***ケース: T(n) = O(n)
最悪の場合: T(n) = O(nlogn)
平均ケース: T(n) = O(nlogn)

6. クイックソート

クイックソートという名前は単純で大雑把です。この名前を聞いた瞬間に、その存在の意味がわかります。つまり、高速で効率的です。これは、ビッグデータを処理するための最速のソートアルゴリズムの 1 つです。

（１）アルゴリズムの紹介

クイックソートの基本的な考え方は、ソートプロセスを通じて、ソートするレコードを 2 つの独立した部分に分けることです。レコードの 1 つの部分のキーワードが他の部分のキーワードよりも小さい場合、レコードの 2 つの部分を個別にソートして、シーケンス全体の順序を実現できます。

（２）アルゴリズムの記述と実装

クイックソートは、分割統治アルゴリズムを使用してリストを 2 つのサブリストに分割します。具体的なアルゴリズムは次のように説明されます。

<1>. シーケンスから「ピボット」と呼ばれる要素を選択します。
<2>. シーケンスを並べ替えて、基本値より小さいすべての要素をベースの前に置き、基本値より大きいすべての要素をベースの後ろに配置します（同じ数字がどちらの側にあってもかまいません）。このパーティションを抜けると、ベンチマークはシリーズの途中になります。これはパーティション操作と呼ばれます。
<3>. 基準値より小さい要素の部分列と基準値より大きい要素の部分列を再帰的にソートします。 Javascript コードの実装:

クイックソートアニメーションのデモンストレーション:

（３）アルゴリズム分析

***ケース: T(n) = O(nlogn)
最悪の場合: T(n) = O(n2)
平均ケース: T(n) = O(nlogn)

7. ヒープソート

ヒープソートは、ヒープの概念を使用してソートする選択ソートであると言えます。

（１）アルゴリズムの紹介

ヒープソートとは、ヒープデータ構造を使用して設計されたソートアルゴリズムを指します。スタックは、完全な二分木を近似し、スタックの特性を満たす構造です。つまり、子ノードのキー値またはインデックスは常に親ノードよりも小さい (または大きい) です。

（２）アルゴリズムの記述と実装

具体的なアルゴリズムは次のように説明されます。

<1>. ソートするキーワードの初期シーケンス（R1、R2…Rn）を、初期の順序付けされていない領域である大きなヒープ内に構築します。
<2>. 最上位要素R[1]を最後の要素R[n]と交換し、新しい順序なし領域（R1、R2、... Rn-1）と新しい順序付き領域（Rn）を取得し、R[1、2...n-1] <= R[n]を満たします。
<3>. 交換後の新しいヒープ最上部R[1]はヒープの特性に違反する可能性があるため、現在の順序付けされていない領域（R1、R2、…Rn-1）を新しいヒープに合わせて調整し、R[1]を順序付けされていない領域の最後の要素と再度交換して、新しい順序付けされていない領域（R1、R2、…Rn-2）と新しい順序付けされた領域（Rn-1、Rn）を取得する必要があります。順序付けられた領域内の要素の数が n-1 になるまでこのプロセスを繰り返し、ソートプロセス全体が完了します。

Javascript コードの実装:

ヒープソートのアニメーションのデモンストレーション:

（３）アルゴリズム分析

***ケース: T(n) = O(nlogn)
最悪の場合: T(n) = O(nlogn)
平均ケース: T(n) = O(nlogn)

8. カウントソート

カウンティングソートの中核は、入力データの値をキーに変換し、それを追加の配列スペースに格納することです。

線形時間計算量を持つソート方法として、カウンティングソートでは、入力データが特定の範囲の整数である必要があります。

（１）アルゴリズムの紹介

カウンティングソートは安定したソートアルゴリズムです。カウントソートでは追加の配列 C が使用されます。ここで、i 番目の要素は、ソートする配列 A 内で値が i に等しい要素の数です。次に、配列 C を使用して、配列 A 内の要素を正しい位置に配置します。整数のみをソートできます。

（２）アルゴリズムの記述と実装

具体的なアルゴリズムは次のように説明されます。

<1>. ソートする配列内の最大要素と最小要素を見つけます。
<2>. 配列内の値 i を持つ各要素の出現回数を数え、それを配列 C の i 番目の項目に格納します。
<3> すべてのカウントを累積します（Cの最初の要素から始めて、各項目を前の項目に追加します）。
<4>. ターゲット配列を逆順に埋めます。各要素 i を新しい配列の C(i) 番目の項目に配置し、要素が配置されるたびに C(i) から 1 を減算します。

Javascript コードの実装:

JavaScript アニメーション画像デモ:

（３）アルゴリズム分析

入力要素が 0 から k までの n 個の整数の場合、実行時間は O(n + k) です。カウンティングソートは比較ソートではなく、そのソート速度はどの比較ソートアルゴリズムよりも高速です。カウント配列 C の長さは、ソートする配列内のデータの範囲 (ソートする配列の最高値と最低値の差に 1 を加えた値) に依存するため、データ範囲が大きい配列の場合、カウントソートには多くの時間とメモリが必要になります。

***ケース: T(n) = O(n+k)
最悪の場合: T(n) = O(n+k)
平均的なケース: T(n) = O(n+k)

9. バケットソート

バケットソートは、カウントソートのアップグレード版です。これは関数のマッピング関係を利用しますが、その効率の鍵はこのマッピング関数の決定にあります。

（１）アルゴリズムの紹介

バケットソートは、入力データが均一に分散されていると想定し、データを有限数のバケットに分割し、各バケットを個別にソートすることによって機能します (別のソートアルゴリズムを使用するか、バケットソートを再帰的に使用し続ける可能性があります)。

（２）アルゴリズムの記述と実装

具体的なアルゴリズムは次のように説明されます。

<1>. 一定量の配列を空のバケットとして設定します。
<2>. 入力データを走査し、データを対応するバケットに1つずつ入れます。
<3>. 空でない各バケットをソートします。
<4>. 空でないバケットからソートされたデータを結合します。

Javascript コードの実装:

バケット分類図（インターネットからの画像）：

（３）アルゴリズム分析

バケットソートでは、最良の場合でも線形時間 O(n) が使用されます。バケットソートの時間計算量は、各バケット間のデータのソートの時間計算量に依存します。これは、他の部分の時間計算量が O(n) であるためです。当然ですが、バケットが小さいほど、バケット間のデータが少なくなり、ソートにかかる時間も短くなります。ただし、それに応じてスペースの消費量も増加します。

***ケース: T(n) = O(n+k)
最悪の場合: T(n) = O(n+k)
平均ケース: T(n) = O(n2)

10. 基数ソート

基数ソートも非比較ソートアルゴリズムであり、最初のビットから始めて各ビットを O(kn) の複雑度でソートします。ここで、k は配列の長さ、k は配列の最初の桁数です。

（１）アルゴリズムの紹介

基数ソートでは、まず下位の順序でソートし、次に集計し、次に上位の順序でソートし、最後に集計し、というように最後の順序までソートします。一部の属性には優先順位があり、最初に低い優先順位で並べ替え、次に高い優先順位で並べ替える場合があります。 *** の順序は、優先度の高いものが先に表示され、優先度が同じ場合は優先度の低いものが先に表示されます。基数ソートは、個別のソートと個別のコレクションに基づいているため、安定しています。

（２）アルゴリズムの記述と実装

具体的なアルゴリズムは次のように説明されます。