面接前に必ず読むべきソートアルゴリズムトップ10

[[419332]]

導入

プログラマーとして、上位 10 のソートアルゴリズムは必須であり、すべての資格のあるプログラマーが習得する必要があります。また、クイックソートやマージソートなどの一般的なアルゴリズムについては、アルゴリズムのパフォーマンスと複雑さの習得を必要とする、より詳細な質問を受ける場合があります。 Java とデータ構造およびアルゴリズムに関する責任あるブロガーとして、bigsai はこの点に関して読者に抜け穴を絶対に残しません。この記事を読んでいただければ、最も一般的な 10 個のソートアルゴリズムを紹介し、簡単に習得できるようにお手伝いします。

まず、ソートに関して言えば、ほとんどの人にとってソートの概念はバブルソートまたは JDK の Arrays.sort() のままです。上位 10 位のソートアルゴリズムは言うまでもなく、さまざまなソートアルゴリズムを手書きすることは多くの人にとって贅沢です。しかし、幸運なことに、あなたはこの記事に出会いました。

ソートの分類には、主に、複雑性、内部と外部、比較的次元と非比較的次元などのさまざまな次元があります。私たちがよく話題にする上位 10 のソートアルゴリズムは、内部ソートです。これらは、「比較と非比較」の次元に基づくソートタイプの 2 つのカテゴリに分類されます。

「非比較ソートには、バケットソート、基数ソート、カウントソートなどがあります。」ソートを8つの主要なソートアルゴリズムにまとめる人も多くいます。これは、基数ソートとカウンティングソートがバケットソートをベースとしていたり、特殊なバケットソートであったりするからですが、基数ソートとカウンティングソートにはそれぞれ独自の特徴があるため、ここでは10の古典的なソートアルゴリズムにまとめています。比較ソートは、
比較ソートは、交換ベース、挿入ベース、選択ベース、マージベースなど、さらに細かいカテゴリに分けることもできます。詳細については、以下のマインドマップを参照してください。

バブルソート

バブルソート (バブルソートとも呼ばれる) は、交換ベースの典型的なソートアルゴリズムであり、クイックソートの考え方の基盤となっています。バブルソートは、時間計算量が O(n^2) の安定したソートアルゴリズムです。基本的な考え方は、「ループを複数回実行し、そのたびに大きな要素を前から後ろへ移動し、そのたびに最大 (最小) 要素を決定し、複数回実行した後にソートされたシーケンスに到達する」というものです (または、小さな要素を後ろから前へ移動します)。

具体的なアイデアは（大きな要素を後ろに調整する）です：

最初の要素から始めて、逆方向にトラバースします。各位置で、次の要素より大きいかどうかを判断します。大きい場合は、2 つのサイズを交換し、逆方向に続行します。このようにして、1 ラウンド後に、 「最大の数字が最後の位置と交換され、決定できる」ことが保証されます。
2 回目も、最初から開始して、前方後方に移動します。現在の位置が次の位置よりも大きい場合は、その次の数字と交換します。ただし、今回は最後まで判断する必要はなく、最後から2番目の位置まで判断するだけでよいことに注意してください（最初に最大のものが最後であると決定したため、今回は最後から2番目のものを決定することが目標です）。
同様に、最初の要素が要素全体を整列させるまで、後続のトラバーサルの長さは毎回 1 ずつ減少します。

たとえば、 2 5 3 1 4のソートプロセスは次のようになります。

実装コードは次のとおりです。

パブリックvoid maopaosort( int [] a) {
 // TODO 自動生成されたメソッドスタブ
( int i=a.length- 1 ;i>= 0 ;i--)の場合
  {
 ( int j = 0 ; j < i ; j++ )の場合
    {
もし(a[j]>a[j+ 1 ])
      {
 intチーム = a[j];
        a[j] = a[j+ 1 ];
        a[j+ 1 ]=チーム;
      }
    }
  }
 }

クイックソート

クイックソートはバブルソートの改良版であり、再帰的な分割統治アプローチを使用して問題を解決します。バブルソートと比較すると、クイックソートは不安定なソートです。最悪の時間計算量は O(n^2)、平均的な時間計算量は O(nlogn)、最良の時間計算量は O(nlogn) です。

クイックソートの基本的な考え方は次のとおりです。

クイックソートでは、シーケンスを 2 つの部分に分割する必要があります。つまり、 「シーケンスの左側にあるすべての数値は、ある数値より小さい」、「シーケンスの右側にあるすべての数値は、ある数値より大きい」です。次に、再帰の考え方を使用して、左側のシーケンスを完全なシーケンスとしてソートし、同様にシーケンスの右側を完全なシーケンスとしてソートします。
この数字は、このシーケンス内でランダムに選択されます。左端の数字、右端の数字、またはもちろんランダムな数字にすることもできます。しかし、 「通常」最適でない状況では、左端の数字を取ります。

実装コードは次のとおりです。

パブリックvoidクイックソート ( int [] a, int左, int右)
 {
 int左 = 低;
 int高さ = 右;
 // 次の 2 つの文の順序を混在させることはできません。混在させると、配列が範囲外になります。 ！ ！とても重要です！ ！ ！
 if (low>high) // 終了するかどうかを決定する条件として
戻る;
 int k=a[low]; //余分なスペースk、左端のものを基準として、最終的に左側がそれより小さく、右側がそれより大きいことを要求します。
 while (low<high) //このラウンドでは、左側がa[low]より小さく、右側がa[low]より大きい必要があります。
  {
 while (low<high&&a[high]>=k) //右側にkより小さい最初のものが見つかったら停止します
    {
      高い - ;
    }
 //これはそれより小さい最初のものを見つけます
    a[low]=a[high]; //ローポジションにする
while (low<high&&a[low]<=k) //lowの右側でkより大きい最初の値を探し、右側のa[high]に置きます。
    {
      低++;
    }
    a[高]=a[低];
  }
  a[low]=k; //値を割り当て、左と右の再帰で分割統治する
  クイックソート(a, 左, 下位1 );
  クイックソート(a, low+ 1 , right);
 }

挿入ソート

直接挿入ソート

直接挿入ソートは、すべてのソートアルゴリズムの中で最も単純なソート方法の 1 つです。学生時代と同じように、私たちは前から後ろに背の高い順に並んでいました。ですから、身長のバラバラな人たちの集団の中では、先頭の人から始めて、自分より背の高い人が前にいたら、すぐに適切な位置に身を置きます。キュー全体の順序は、「キューの最後のものが挿入されるまで」のみ維持されます。

直接挿入ソートのトラバーサル比較の時間計算量は毎回 O(n) であり、交換の時間計算量も毎回 O(n) であるため、n 回の合計時間計算量は O(n^2) です。バイナリ挿入を O(nlogn) に最適化できるかどうか疑問に思う人もいるかもしれません。答えは「いいえ」です。バイナリ検索では、検索の複雑さを毎回 O(logn) までしか減らすことができませんが、挿入時間の複雑さは毎回 O(n) なので、合計時間複雑さレベルは依然として O(n^2) です。

挿入ソートの具体的な手順は次のとおりです。

現在の位置を選択します (現在の位置より前のデータはすでに整列しています)。目標は、現在の位置のデータをその前の適切な位置に挿入することです。
挿入する場所を見つけるには、前方に列挙するか、バイナリ検索を実行します。
配列を移動し、値を割り当てたり交換したりして挿入効果を実現します。

実装コードは次のとおりです。

パブリックvoid挿入ソート ( int a[])
 {
 intチーム = 0 ;
 ( int i = 1 ;i<a.length;i++)の場合
  {
    System.out.println(Arrays.toString(a));
    チーム=a[i];
 ( int j=i- 1 ;j>= 0 ;j--)の場合
    {
もし(a[j]>チーム)
      {
        a[j+ 1 ] = a[j];
        a[j]=チーム;
      }
それ以外{
壊す;
      }
    }
  }
 }

シェルソート

直接挿入ソートは O(n^2) なので、データ量が多い場合やデータの移動回数が多すぎる場合には効率が悪くなります。多くのソート方法は、シーケンスを分割してから結合しようとします。シェルソートは、「データ量と順序」という 2 つの側面を考慮してアルゴリズムを設計し、特別な方法で前処理を実行します。できるだけ小さいものを前に、大きいものを後ろにして、グループ化の計算を数回実行し、最後のグループは完全な直接挿入ソートになります。

长串の場合、ヒルは最初にシーケンスを分割しますが (非線形分割)、 「特定の数値係数に従って」分割します(取余、数字 1、2、3、4 を報告することに似ています。1、2、3、4)。このように、分割のグループの形式で、「各グループを直接挿入して個別に並べ替える」ため、 「後ろにある非常に小さな数字」を「より少ない回数」で「比較的前の位置に移動する」ことができます。その後、ゆっくりと融合して長くし、少しだけ動かします。

このような挿入を行うたびにシーケンスの順序が整えられるため、わずかに順序付けられたシーケンスに対して直接挿入ソートを実行してもコストはかかりません。したがって、合併が完了すると、小さい方が前に出て、大きい方が後ろに来ることになり、コストはどんどん小さくなります。このように、シェルソートでは挿入ソートに比べて多くの時間を節約できます。

実装コードは次のとおりです。

パブリックvoidシェルソート ( int a[])
 {
 int d = a.長さ;
 int team = 0 ; //一時変数
for (;d>= 1 ;d/= 2 ) // d グループに分割
for ( int i=d;i<a.length;i++) //その要素を取得するには、その要素が含まれているグループを確認するだけです。
    {
      チーム=a[i];
 ( int j=id;j>= 0 ;j-=d)の場合
      {
もし(a[j]>チーム)
        {
          a[j+d] = a[j];
          a[j]=チーム;
        }
それ以外{
壊す;
        }
      }
    }
 }

クラスソートを選択

単純な選択ソート

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

実装コードは次のとおりです。

パブリックvoid selectSort( int [] arr) {
 ( int i = 0 ; i < arr.length - 1 ; i++) {
 int min = i; // 最小位置
( int j = i + 1 ; j < arr.length; j++) {
 （arr[j] < arr[min]）の場合{
        min = j; // 最小位置を変更する
      }
    }
 （最小値 != i）の場合{
      swap(arr, i, min); // i番目の位置と交換
    }
  }
 }
プライベートvoid swap( int [] arr, int i, int j) {
 temp = arr[i];
  arr[i] = arr[j];
  arr[j] = 一時;
 }

ヒープソートは、まずヒープを基準に行われます。ヒープは完全な二分木です。まず、大きなルートヒープと小さなルートヒープを理解する必要があります。完全な二分木のすべてのノードは、その子ノードよりも大きい (または小さい) ため、ここでは 2 つのケースがあります。

すべてのノードが子ノードの値よりも「大きい」場合、このヒープは「ビッグルートヒープ」と呼ばれ、ヒープの最大値はルートノードにあります。
すべてのノードが子ノードの値よりも「小さい」場合、このヒープは「小さなルートヒープ」と呼ばれ、ヒープの最小値はルートノードにあります。

ヒープソートでは、まず「ヒープを構築」し、次にそれを調整します。バイナリツリー (配列表現) の場合、 「最初の非リーフノード」から始めて、下から上に向かって調整します。調整のルールは次のとおりです。

ヒープ構築は、時間計算量が O(n) のプロセスです。ヒープ構築後、ヘッドソートを実行する必要があります。配列を指定してヒープを作成する (createHeap)

① 現在のノードとその子がヒープの特性を維持できるように、最初の非リーフノードからスワップダウン（shiftDown）の判断を開始します。

②ただし、通常のノードの交換では問題ないかもしれません。交換によって子ヒープ構造の特性が破壊される場合は、交換したノードを再び停止するまでシフトダウンする必要があります。

ヒープが構築され、最初の最上位要素が最小 (最大) として取得されます。残りの左と右の子はヒープのプロパティ値を満たしていますが、最上位要素が欠落しています。子を上に移動すると、移動される要素が多すぎてヒープ構造が破壊される可能性があります。

①最後の要素を最初に置くだけです。このように、スワップダウン（shiftDown）の判定だけ行えば良いのですが、このときヒープ全体のサイズが変わっていることに注意が必要です。放棄した位置を論理的に利用することはないので、関数設計時にはヒープサイズのパラメータが必要になります。

②ヒープ内のすべての要素が取得されるまで、上記の手順を繰り返します。

ヒープアルゴリズムの複雑さの分析では、ヒープ構築の時間計算量は以前は O(n) でした。ヒープの先頭が削除されるたびに、下方向にスワップする必要があり、それぞれの最悪数は logn になります。これにより、複雑さは O(nlogn) になります。合計時間複雑さは O(n)+O(nlogn)=O(nlogn) です。

実装コードは次のとおりです。

静的void swap( int arr[], int m, int n)
 {
 intチーム = arr[m];
  arr[m] = arr[n];
  arr[n]=チーム;
 }
 //下に移動してスワップし、現在のノードをヒープ（小さなルート）に効果的に変換します。
 static void shiftDown( int arr[], int index, int len) // 位置0は使用されません
{
 int leftchild=index* 2 + 1 ; // 左の子
int rightchild=index* 2 + 2 ; //右の子
(左の子>=長さ)の場合
戻る;
 else if (rightchild<len&&arr[rightchild]<arr[index]&&arr[rightchild]<arr[leftchild]) //右の子は範囲内にあるので、交換する必要があります
  {
    swap(arr, index, rightchild); //ノードの値を入れ替える
    shiftDown(arr, rightchild, len); //子ノードのヒープに影響する可能性があり、下方向に再構築します
  }
 else if (arr[leftchild]<arr[index]) //左の子を交換
  {
    swap(arr, インデックス, 左の子);
    shiftDown(arr, leftchild, len);
  }
 }
 //スタックに配列を作成する
静的void createHeap( int arr[])
 {
 ( int i=arr.length/ 2 ;i>= 0 ;i--)の場合
  {
    シフトダウン(arr, i,arr.length);
  }
 }
静的voidヒープソート( int arr[])
 {
  System.out.println( "元の配列は: " +Arrays.toString(arr));
 int val[] = new int [arr.length]; //一時保存結果
//ステップ1 ヒープ構築
  ヒープを作成します(arr);
  System.out.println( "ヒープ構築後のシーケンスは次のとおりです: " + Arrays.toString(arr));
 //ステップ 2: n 値のフェッチを実行してヒープを作成し、そのたびにヒープの最上位要素をフェッチして val 配列に格納します。最終結果は昇順でソートされたシーケンスになります。
 ( int i = 0 ;i<arr.length;i++)の場合
  {
    val[i]=arr[ 0 ]; //ヒープの先頭を結果に格納する
    arr[ 0 ] = arr[arr.length- 1 -i]; // ヒープの先頭の要素を削除し、最後の要素をヒープの先頭に置く
    shiftDown(arr, 0 , arr.length-i); //このヒープを合法的な小さなルートヒープに調整します。(論理的な)長さが変更されていることに注意してください。
  }
 //数値クローンコピー
( int i = 0 ;i<arr.length;i++)の場合
  {
    arr[i] = val[i];
  }
  System.out.println( "ヒープソート後のシーケンスは次のとおりです:" +Arrays.toString(arr));
 }

マージクラスソート

マージソートでは、通常はマージソートについてのみ説明しますが、マージソートは双方向マージと多方向マージにも分けられます。ここでは、双方向マージソートについてさらに詳しく説明し、再帰的に実装します。

マージソート

マージとクイックソートはどちらも「分割統治アルゴリズムに基づいています」 。分割統治アルゴリズムは実際には多くの用途があり、多くの分割統治アルゴリズムは再帰を使用しますが、実際には「分割統治と再帰は異なるものです」 。分割統治とは分割統治を意味し、再帰的に実装することも、非再帰的な方法でプロセス全体を自分で走査することによって実装することもできます。マージソートは、まず問題をコストの低いサブ問題に分解し、次にコストの低いサブ問題をマージしてソートを完了します。

マージの背後にある考え方は次のとおりです。

1 回目: 文字列全体が個々の文字列に分割されます。最初は、シーケンス ( 1 2 3 4 5 6--- ) 内の 2 つを順序付けられたシーケンスにマージし、次に ( xx xx xx xx---- ) をローカルに順序付けられたシーケンスにマージします。
2回目は、2つずつを4つの数字（ 1 2 3 4 5 6 7 8 ---- ）に結合します。 「各小さな部分は順序どおりです」 。
これは、文字列が 1 つだけ残るまで続きますが、消費される合計回数は logn です。各操作の時間計算量は再びO(n)です。したがって、合計時間計算量はO(nlogn)です。

O(n) プロセスに統合:

実装コードは次のとおりです。

プライベート静的voidマージソート( int []配列、 int左、 int右) {
 int中央 = (左 + 右) / 2 ;
 （左<右）の場合
  {
    マージソート(配列、左、中央);
    マージソート(配列、中央+ 1 、右);
    マージ(配列、左、中央、右);
  }
 }
プライベート静的voidマージ( int []配列、 int l、 int mid、 int r) {
 int lindex=l; int rindex=mid+ 1 ;
 intチーム[] =新しいint [r-l+ 1 ];
 intチームインデックス = 0 ;
 while (lindex<=mid&&rindex<=r) { //まず左と右を比較してマージする
(配列[lindex]<=配列[rindex])の場合
    {
      チーム[チームインデックス++]=配列[lindex++];
    }
それ以外{
      チーム[チームインデックス++]=配列[rindex++];
    }
  }
 while (lindex<=mid) // 1つが制限を超えた場合、残りのものは順番に追加されます
  {
    チーム[チームインデックス++]=配列[lindex++];
  }
 (rindex<=r)の場合
  {
    チーム[チームインデックス++]=配列[rindex++];
  }
 ( int i = 0 ;i<teamindex;i++)の場合
  {
    配列[l+i]=チーム[i];
  }
 }

バケットソート

バケットソートは、スペースと時間をトレードするソートです。バケットソートで重要なのは、そのアイデアであり、具体的な実装ではありません。最適な時間計算量は線形 O(n) かもしれません。バケットソートは、比較ベースのソートではなく、分散ベースのソートです。バケットソートは文字通り次のことを意味します:

バケット: 複数のバケット。このタイプのソートではデータが複数のバケットに分けられることを示します。
バケット: 各バケットには容量があります。バケットは一定の容量を持つコンテナなので、各バケットには複数の要素が含まれる場合があります。
バケット: 全体的な観点から、ソート全体では、バケットのバランスがより良くなること、つまり、あふれたり (多すぎたり) 少なすぎたりしないことが期待されます。

バケットソートの考え方は、「ソートするシーケンスを複数のバケットに分割し、各バケット内の要素を個別にソートする」というものです。もちろん、バケットソートのスキームは特定のデータに関連しています。バケットソートは比較的広い概念であり、カウントソートは特別なバケットソートです。基数ソートもバケットソートに基づいています。データが均等に分散され、各バケット要素が 1 に近づくと、時間計算量は O(n) に達する可能性があります。ただし、データ範囲が大きく、比較的集中している場合は、バケットソートの使用は適していません。

単純なバケットソートを実装します。

 java.util.ArrayListをインポートします。
 java.util.Listをインポートします。
 // WeChat パブリックアカウント: bigsai
パブリッククラスbucketSort {
パブリック静的voidメイン(String[] args) {
 int a[] = { 1 、 8 、 7 、 44 、 42 、 46 、 38 、 34 、 33 、 17 、 15 、 16 、 27 、 28 、 24 };
  List[] バケット =新しいArrayList[ 5 ];
 for ( int i = 0 ;i<buckets.length;i++) //初期化
  {
   バケット[i] =新しいArrayList<Integer>();
  }
 for ( int i = 0 ;i<a.length;i++) //ソートするシーケンスを対応するバケットに格納します
  {
 int index=a[i]/ 10 ; //対応するバケット番号
   バケット[インデックス].add(a[i]);
  }
 for ( int i = 0 ; i < buckets.length; i++) // 各バケットをソートする（システム独自のクイックソートを使用）
  {
   バケット[i].sort( null );
 for ( int j = 0 ; j < buckets [i]. size (); j ++) // ちなみに出力を印刷する
   {
    System.out.print(buckets[i].get(j)+ " " );
   }
  }
 }
 }

カウントソート

カウントソートは特殊なバケットソートです。各バケットのサイズは 1 です。各バケットはリストで表されなくなり、通常はカウントに値を使用します。

特定のアルゴリズムを設計するときは、まず最小値 min を見つけ、次に最大値 max を見つけます。次に、この間隔サイズの配列を作成し、最小位置からカウントを開始すると、スペースを最大限に圧縮して、スペースの利用効率を向上させることができます。

パブリック静的void countSort( int a[])
 {
 int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE;
 for ( int i = 0 ;i<a.length;i++) // 最大値と最小値を見つける
  {
もし(a[i]<min)
      最小値=a[i];
もし(a[i]>max)
      最大値 = a[i];
  }
 int count[] = new int [max-min+ 1 ]; // 要素を数える
( int i = 0 ;i<a.length;i++)の場合
  {
    count[a[i]-min]++;
  }
 // 値をソートする
整数インデックス = 0 ;
 ( int i = 0 ;i<count.length;i++)の場合
  {
 (count[i] --> 0 )の間{
      a[index++]=i+min; //minは真の値
    }
  }
 }

基数ソート

基数ソートは、理解するのは簡単ですが、実装 (最適化) が難しいアルゴリズムです。基数ソートはカードソートとも呼ばれます。基数ソートの原理はカウンティングソートを複数回使うことですが（カウンティングソートは特殊なバケットソートです）、これまでの普通のバケットソートやカウンティングソートと異なるのは、 「基数ソートは全体をバケットに割り当てるのではなく、それ自体を個々の要素に分割し、各要素を順にバケットに割り当てて順番に集めていく」という点です。前から後ろへ、または後ろから前へという順番で各位置を割り当てて集めていくと、順序のあるシーケンスが得られます。

ソートが数値型の場合、このバケットには 0 から 9 までの数字のみを含める必要がありますが、文字型の場合は ASCII の範囲に注意する必要があります。

このような状況に遭遇した場合、基数ソートの考え方は非常にシンプルです。934、241、3366、4399の基数ソートのプロセスを例に挙げてみましょう。最初は、各桁に応じて割り当てと収集を行います。

割り当てと収集は両方とも順序どおりです。2 回目の割り当てと収集は、10 の位に基づいて行われます。今回は、1 回目の割り当てと収集が 1 の位に基づいているため、1 の位と 10 の位だけを見ると、すべての数字が順序どおりになっています。

3回目は百の位を分配して集める時間です。この時間以降は百の位以下が順番になります。

最後に処理するときに、千の位のいくつかの桁にゼロを埋め込む必要があります。これが完了すると、最後の千の位とそれ以降の桁が整列し、シーケンス全体がソートされます。

簡単な実装コードは次のとおりです。

 static void radixSort( int [] arr) //右から左へのint型
{
  List<Integer> バケット[] =新しいArrayList[ 10 ];
 ( int i = 0 ; i < 10 ; i++)の場合
  {
    バケット[i] =新しいArrayList<Integer>();
  }
 // 最大値を見つける
int max = 0 ; //すべて正の数であると仮定
( int i = 0 ;i<arr.length;i++)の場合
  {
もし（arr[i]>max）
      最大値=arr[i];
  }
 int divisionNum = 1 ; //1 10 100 100… 対応する数値を見つけるために使用
while (max> 0 ) { //maxとnumの制御
for ( int数値: 配列 )
    {
      bucket[(num/divideNum)% 10 ].add(num); //対応する位置の数字を対応するバケットに割り当てる
    }
    除算数* = 10 ;
    最大/ = 10 ;
整数idx = 0 ;
 // 再度データを収集して取得する
for (List<Integer> リスト: バケット)
    {
 for ( int数値:リスト)
      {
        arr[idx++] = 数値;
      }
      list.clear(); //収集後はクリアして将来使用するために保存する必要があります
    }
  }
 }

もちろん、等長文字列と不等長文字列、1次元配列の最適化など、学ぶべき基数ソートの実装は様々あります。詳細については、公式アカウントの他の記事を参照してください。

今回はトップ10ランキングをざっくりと振り返りました。皆さんもなんとなくわかっていただけるかと思います！アルゴリズムの概要については、不必要な労力を避けるために、次の表を共有します。

ソートアルゴリズム	平均時間計算量	ほとんど	最悪	空間の複雑さ	安定性
バブルソート	（n^2）	の上）	（n^2）	オー(1)	安定させる
クイックソート	O(nlogn)	O(nlogn)	（n^2）	O(logn)	不安定
挿入ソート	（n^2）	の上）	（n^2）	オー(1)	安定させる
シェルソート	O(n^1.3)	の上）	O(nlog2n)	オー(1)	不安定
選択ソート	（n^2）	（n^2）	（n^2）	オー(1)	不安定
ヒープソート	O(nlogn)	O(nlogn)	O(nlogn)	オー(1)	不安定
マージソート	O(nlogn)	O(nlogn)	O(nlogn)	の上）	安定させる
バケットソート	O(n+k)	O(n+k)	O(n+k)	O(n+k)	安定させる
カウントソート	O(n+k)	O(n+k)	O(n+k)	わかりました）	安定させる
基数ソート	O(n*k)	O(n*k)	O(n*k)	O(n+k)	安定させる